THPT Chuyên Bến Tre

“Bên phaaaaải quay!” “Bên traaaaái quay!” ‘Đằng saaaau quay!” Người trung sỹ hô rát họng nhưng đám tân binh vẫn quay láo nháo, không phân biệt đâu là bên phải, đâu là bên trái, cũng có thể họ nghĩ rằng “Bên trái quay!” là quay sang phía bên trái của người cạnh mình. Cuối cùng thì trung sỹ cũng hiểu ra rằng trước mặt mình là lớp người thế hệ Internet, chỉ quen nhấp chuột và hiểu rất nhanh các lệnh lập trình, chơi trò chơi trên máy tính cực kỳ thành thạo. Anh quyết định thay đổi cách huấn luyện và việc đầu tiên là dạy họ phân biệt bên phải bên trái.

Trung sỹ đánh số mọi người từ 1 đến n (1 ≤ n ≤ 1.000.000) và chia làm hai nhóm “đứng trong hàng” và “đám đông”. Ban đầu trong hàng chỉ có ngưới số 1. Những người đứng trong hàng tạo thành một hàng ngang và quay mặt về một phía. Trung sỹ ra lệnh và mọi người thực hiện. Mỗi lệnh có một trong 4 dạng sau:

• left i j – người i trong đám đông chạy vào hàng và đứng bên trái, cạnh người j,
• right i j – người i trong đám đông chạy vào hàng và đứng bên phải, cạnh người j,
• leave i – người i ra khỏi hàng trở về đám đông,
• name i – yêu cầu người i nói số của người bên trái và số của người bên phải mình. Nếu i đứng ở đầu hoặc cuối hàng thì một trong hai số cần nói sẽ là 0.

Các câu lệnh đều đúng ngữ cảnh và hàng không bao giờ rỗng.

Đôi khi hàng trở nên quá lớn và trung sỹ không biết được câu trả lời của người tân binh là đúng hay sai.

Yêu cầu: Cho n, số câu lệnh m (1 ≤ m ≤ 1.000.000) và các câu lệnh theo trình tự cần thực hiện. Hãy đưa ra kết quả các câu lệnh dạng name i.

Input

• Dòng đầu tiên chứa 2 số nguyên n và m,
• Mỗi dòng trong m dòng sau chứa một câu lệnh.

Output

• Mỗi dòng chứa 2 số nguyên là  kết quả câu lệnh name i.

Example

Input:

3 5

left 2 1

right 3 1

name 1

leave 1

name 2

Output:
2 3

0 3

* Ghi chú:

• 50% test có 1 <= N , M <= 1000