Tram

To ease the traffic jams in Seoul, mayor Kim Sang-geun brought in a tram. The seats of the tram form a grid of $N$ rows and 2 columns. The rows are numbered 1 through $N$, and the columns are numbered 1 and 2.

The distance between seats $(R_A, C_A)$ and $(R_B, C_B)$ is the distance between the centers of the two cells, $\sqrt{(R_A-R_B)^2+(C_A-C_B)^2}$.

Most people sit as far away from the other passengers as they can. When a passenger steps into the tram, they measure for every empty seat the distance from that seat to the nearest seated passenger, and they take the seat where that distance is largest. When several seats tie, they take the one with the smaller row number, and when the row number ties as well, the one with the smaller column number. A passenger who has sat down stays in that seat until leaving the tram. A passenger who boards an empty tram sits in row 1, column 1.

You are given the log of passengers boarding and leaving. Write a program that reports the seat each passenger takes.

The log has $M$ lines, numbered 1 through $M$ in the order given. There are two kinds of lines. 'E' means a passenger boarded, and 'L' means a passenger left. A line that records a departure also tells on which line that passenger boarded.

A boarding line appears only when at least one seat is empty.

The first line contains the number of rows $N$ and the number of log lines $M$. ($1 \le N \le 150{,}000$, $1 \le M \le 30{,}000$)

Each of the next $M$ lines records a boarding or a departure. When line $K$ is 'L', it comes with $P_K$ ($1 \le P_K \le K$), meaning that the passenger who boarded on line $P_K$ leaves. Line $P_K$ is always 'E', and no passenger leaves twice.

Every time an 'E' line is given, print on its own line the row number and the column number of the seat that passenger takes, separated by a single space.