Места в новом трамвае в Загребе организованы в виде сетки, состоящей из \(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\) в том порядке, в котором они произошли. Существует два вида событий: событие типа «Е» соответствует пассажиру, входящему в трамвай, а событие типа «L» соответствует пассажиру, покидающему трамвай. Для события типа «L» также дается целое число \(P\) - оно указывает, что уходящий пассажир - это тот, который зашел в трамвай во время события \(P\).

Гарантируется, что в трамвае всегда будет хотя бы одно свободное место, когда пассажир пытается войти.