Tại nhà ăn mới của học viện Lam Kiều, các học sinh xếp thành một hàng dài trước quầy lấy đồ ăn. Lan, quản lý nhà ăn, muốn nắm được theo thời gian thực số hiệu của học sinh đứng đầu và đứng cuối hàng.

Bạn cần thực hiện ba loại thao tác sau:

1. Học sinh vào hàng: học sinh có số hiệu $x$ xếp vào cuối hàng.

2. Học sinh rời hàng: học sinh đứng đầu hàng nhận đồ ăn rồi rời khỏi hàng.

3. Truy vấn trạng thái hàng: in ra số hiệu của học sinh đứng đầu và đứng cuối hàng hiện tại.

Lưu ý, các học sinh có thể quay lại xếp hàng sau khi ăn xong.

Dữ liệu vào

Đầu tiên, bạn nhận được một số nguyên $q$, biểu thị số thao tác cần thực hiện.

$q$ dòng tiếp theo, mỗi dòng chứa một hoặc hai số nguyên, biểu thị một thao tác:

• 1 x: học sinh có số hiệu $x$ vào hàng.

• 2: học sinh đứng đầu nhận đồ ăn và rời khỏi hàng.

• 3: in ra số hiệu học sinh đứng đầu và đứng cuối hàng hiện tại (hai số hiệu cách nhau một dấu cách).

Dữ liệu ra

Với mỗi thao tác 3, in ra một dòng gồm hai số nguyên, là số hiệu của học sinh đứng đầu và đứng cuối hàng hiện tại.

Ví dụ

Input

5
1 1
1 3
3
2
3

Output

1 3
3 3

Ghi chú

Giải thích ví dụ

Với ví dụ đã cho, hàng thay đổi như sau:

1. Học sinh số hiệu $1$ vào hàng, hàng trở thành $q = [1]$.

2. Học sinh số hiệu $3$ vào hàng, hàng trở thành $q = [1, 3]$.

3. In ra số hiệu học sinh đứng đầu và đứng cuối hàng, lần lượt là $1$ và $3$.

4. Học sinh đứng đầu nhận đồ ăn và rời hàng, hàng trở thành $q = [3]$.

5. In ra số hiệu học sinh đứng đầu và đứng cuối hàng, lần lượt là $3$ và $3$.

Giới hạn dữ liệu

• $1 \leq x, q \leq 10^5$

• Khi thực hiện thao tác 2 và 3, hàng chắc chắn không rỗng.

• Số hiệu của mỗi học sinh là duy nhất.