Во время пандемии 2020 года, в школе Маши, Даши и Миши переоборудовали столовую с учетом требований соблюдения дистанции. Для каждого класса все столы были одноместные и расставлялись в виде сетки, состоящей из
\(N\) рядов, пронумерованных от
\(1\) до
\(N\), и двух столбцов, пронумерованных от
\(1\) до
\(2\). Расстояние между столами
\((R_a, C_a)\) и
\((R_b, C_b)\) равно евклидому расстоянию между центрами соответствующих клеток, а именно
\(\sqrt {(R_a - R_b)^2 + (C_a - C_b)^2}\)
Каждый ученик класса, приходя в столовую, размещается как можно дальше от других учеников. Точнее говоря, дежурный класса назначает ученику свободное место, расстояние от которого до ближайшего занятого места максимально. Если имеется более одного такого места, то дежурный всегда назначает место с номером в меньшем ряду, а если есть несколько таких мест, он выбирает место с наименьшим столбцом. После того, как дежурный назначил место, учащийся должен сидеть только за этим столом до окончания обеда, после обеда учащийся покидает столовую, сообщая об этом дежурному. Если в столовой никого нет, то входящему учащемуся всегда назначается место в ряду 1 и столбце 1.
В школе Маши, Даши и Миши все ученики прилежные и всегда занимают те места, которые им были указаны.
Но так как дежурные иногда задерживаются на уроках, они просят Вас написать программу, которая учитывая последовательность событий и тип каждого события, автоматически назначала бы место для учащегося. Изначально столовая пуста.
События нумеруются от
\(1\) до
\(M\) в том порядке, в котором они происходят. Существует два вида событий: событие типа
"E" соответствует учащемуся, купившему обед, и которому нужен стол, а событие типа
"L" соответствует учащемуся, который закончил обедать и освободил вышел из-за стола. Для события типа
"L" также дается число
P - оно указывает, что уходящий ученик - это тот, который купил обед во время события
P.
Гарантируется, что в столовой всегда будет хотя бы одно свободное место, когда учащийся купил для себя обед.
Входные данные: Первая строка содержит два целых числа
N и
M (
1 <= N <= 150000, 1 <= M <= 30000), количество рядов в словой и количество событий. Следующие
M строк содержат описание событий,
K-я из этих строк содержит описание события
K - либо символ «
E», либо символ «
L», за которым следует целое число
Pk (
1 <= Pk < K). Гарантируется, что событие
Pk относится к типу «
E», и ни один учащийся не будет пытаться уйти из столовой дважды.
Выходные данные: Для каждого события типа «
E» в том порядке, в котором они произошли, выведите строку и номер столбца места, на которое должен сесть учащийся
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 7
E
E
E
L 2
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
L 6
E |
1 1
10 2
5 2
7 1
4 2
2 2
4 1 |