Олимпиадный тренинг

Задача 37709. Keep your distance!


Задача

Темы: Множества
During the 2020 pandemic, at Masha, Dasha and Misha's school, the canteen was refurbished to comply with social distancing requirements. For each class, all tables were single and arranged in a grid consisting of \(N\) rows, numbered from \( 1\) to \(N\), and two columns numbered from \(1\)< /span> to \(2\). Distance between tables \((R_a, C_a)\) and \((R_b, C_b)\) equals the Euclidean distance between the centers of the corresponding cells, namely \(\sqrt {(R_a - R_b)^2 + (C_a - C_b)^2}\)
Each student in the class, coming to the dining room, is placed as far as possible from other students. More precisely, the class attendant assigns the student a free place, the distance from which to the nearest occupied place is maximum. If there is more than one such seat, then the attendant always assigns the seat with the number in the smallest row, and if there are several such seats, he chooses the seat with the smallest column. After the duty officer has appointed a place, the student should only sit at this table until the end of lunch, after lunch the student leaves the dining room, informing the duty officer about this. If no one is in the cafeteria, the incoming student is always assigned a seat in row 1 and column 1. 
At the school of Masha, Dasha and Misha, all the students are diligent and always take the places that they were assigned.
But since attendants are sometimes late in class, they ask you to write a program that, given the sequence of events and the type of each event, would automatically assign a seat to the student. Initially, the dining room is empty.
Events are numbered from \(1\) to \(M\) in the order in which they occur . There are two kinds of events: an event of type "E" corresponds to a student who has bought lunch and needs a table, and an event of type "L" corresponds to a student who has finished lunch and freed left the table. For an event of type "L", a number P is also given - this indicates that the outgoing student is the one who bought lunch at the time of the P event .
It is guaranteed that there will always be at least one free seat in the cafeteria when a student buys their own lunch.

Input: The first line contains two integers N and M ( 1 <= N <= 150000, 1 <= M <= 30000), the number of rows per word, and the number of events. The following M lines contain a description of the event, K-th of these lines contains a description of the event K - or the symbol « ;E", or the character "L" followed by an integer Pk (1 <= Pk < K). The Pk event is guaranteed to be of type «E» and no student will try to leave the cafeteria twice .
Output: For each event of type «E» in the order in which they happened, output the row and column number of the seat where the student should sit

 

Examples
# Input Output
1 3 7
E
E
E
L2
E
L 1
E
1 1
3 2
1 2
3 1
1 1
2 13 9
E
E
E
E
E
E
E
E
E
1 1
13 2
7 1
4 2
10 1
2 2
3 1
5 1
6 2
3 10 9
E
E
E
E
L 3
E
E
L6
E
1 1
10 2
5 2
7 1
4 2
2 2
4 1