전차

서울의 교통 정체를 풀려고 김상근 시장이 전차를 들여왔다. 전차의 좌석은 $N$행 2열 격자다. 행에는 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열에 앉는다.

전차에 탄 승객과 내린 승객의 기록이 주어진다. 각 승객이 어느 좌석에 앉는지 구하는 프로그램을 작성하시오.

기록은 $M$줄이고, 입력에 주어진 순서대로 1번부터 $M$번이다. 기록은 두 종류다. 'E'는 승객이 탔다는 뜻이고, 'L'은 승객이 내렸다는 뜻이다. 내린 기록에는 그 승객이 몇 번째 기록에서 탔는지도 함께 주어진다.

승객이 타는 기록은 빈 좌석이 하나 이상 남아 있을 때만 주어진다.

첫째 줄에 행의 수 $N$과 기록의 수 $M$이 주어진다. ($1 \le N \le 150{,}000$, $1 \le M \le 30{,}000$)

다음 $M$개 줄에 승객의 탑승과 하차 기록이 주어진다. $K$번째 줄이 'L'이면 $P_K$ ($1 \le P_K \le K$)가 함께 주어지고, $P_K$번째 기록에서 탄 승객이 내린다는 뜻이다. $P_K$번째 기록은 항상 'E'이며, 한 승객이 두 번 내리는 경우는 없다.

'E'가 주어질 때마다 그 승객이 앉은 좌석의 행 번호와 열 번호를 공백 하나로 구분해 한 줄에 출력한다.