HP SCHOOL là một ngôi trường nổi tiếng tại thành phố HD. Toàn trường có 4 lớp học.

Vào mỗi buổi sáng, học sinh của 4 lớp xếp hàng để vào trường. Việc xếp hàng được thực hiện như sau:

• Khi một học sinh mới đến, học sinh này sẽ đi vào cuối hàng. Sau đó, học sinh nhìn về phía trước, tìm học sinh gần nhất thuộc cùng lớp với mình và di chuyển đến đứng ngay sau học sinh đó.
• Khi giáo vụ gọi một học sinh vào trường, học sinh đầu hàng sẽ được điểm danh và vào trường.

Có Q truy vấn. Mỗi truy vấn thuộc một trong hai loại:

• Truy vấn E x y: Một học sinh mới đến trường, thuộc lớp x (1 ≤ x ≤ 4) và có tên là y (1 ≤ y ≤ 50000). Các học sinh trong cùng một lớp có tên khác nhau.

• Truy vấn D: Giáo vụ gọi một học sinh vào trường. Hãy cho biết lớp và tên của học sinh được gọi vào.

INPUT

• Dòng đầu tiên chứa số nguyên dương Q (1 ≤ Q ≤ 10⁵), là số lượng truy vấn;
• Q dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong hai dạng:
  • E x y: Thêm một học sinh thuộc lớp x, có tên y vào hàng;
  • D: Gọi học sinh đầu hàng vào trường.

OUTPUT

Với mỗi truy vấn D, nếu hàng không rỗng, in ra hai số nguyên:

• Số thứ nhất là lớp của học sinh được gọi;
• Số thứ hai là tên của học sinh đó.

Ví dụ

Sample Input

5
E 1 1
E 2 1
E 1 2
D
D

Sample Output

1 1
1 2

Giải thích

Sau truy vấn E 1 1:

(1, 1)

Sau truy vấn E 2 1:

(1, 1) (2, 1)

Sau truy vấn E 1 2, học sinh lớp 1 tìm học sinh lớp 1 gần nhất là (1, 1) và đứng ngay sau bạn đó:

(1, 1) (1, 2) (2, 1)

Truy vấn D đầu tiên gọi học sinh:

1 1

Hàng còn lại:

(1, 2) (2, 1)

Truy vấn D tiếp theo gọi học sinh:

1 2

```