시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 20 1 1 50.000%

문제

서울의 교통 정체를 해소하기 위해서 김상근 시장은 전차를 도입했다. 전차의 좌석은 N행 2열로 이루어진 격자 형태이다. 행은 1부터 N까지 번호가 매겨져 있고, 열은 1과 2로 번호가 매겨져 있다.

두 좌석 (RA, CA)와 (RB, CB) 사이의 거리는 각 정사각형의 중이 떨어진 거리로 \(\sqrt{(R_A-R_B)^{2}+(C_A-C_B)^{2}}\) 이다.

대부분의 사람들은 대중 교통을 이용할 때, 다른 승객들과 되도록 멀리 떨어져서 앉으려고 한다. 즉, 승객이 전차 안에 들어서면 각각의 빈 자리에 대해서 그 자리와 가장 가까운 사람이 앉아있는 자리와의 거리를 계산하고, 그 값이 가장 큰 자리에 앉게 된다. 그러한 자리가 여러개인 경우에는 행의 번호가 작은 자리에 앉고, 행의 번호가 작은 자리도 여러개라면 열의 번호가 작은 자리에 앉게 된다. 자리를 한 번 앉으면 열차에서 내릴때까지 계속 그 자리에 앉아있게 된다. 열차가 비어있는 경우에 탑승한 승객은 1행 1열 자리에 앉게 된다.

전차에 탑승한 승객의 하차한 승객의 정보가 주어진다. 이 때, 각 승객이 어떤 자리에 앉는지 구하는 프로그램을 작성하시오.

정보는 총 M줄로 이루어져 있으며, 입력으로 주어진 순서대로 1번부터 M번이다. 총 두 종류의 정보가 존재하며, 'E'는 전차에 탑승한 정보, 'L'은 전차에서 하차한 정보이다. 하차한 정보가 주어질 때는, 몇 번째 정보에서 탑승한 손님인지도 함께 주어진다.

승객이 탑승하는 정보가 주어질 때는 빈 자리가 적어도 하나 있는 데이터만 입력으로 주어진다.

입력

첫째 줄에 행의 수 N과 정보의 수 M이 주어진다. (1 ≤ N ≤ 150,000, 1 ≤ M ≤ 30,000) 다음 M개 줄에는 승객의 탑승 및 하차 정보가 주어진다. 'L'이 주어진 경우에는 PK (1 ≤ PK ≤ K)가 함께 주어지며, PK번째 정보에서 탑승한 손님이 내린다는 뜻이다. 항상 PK번째 정보는 'E'이며, 한 승객이 두 번 내리는 경우는 없다.

출력

'E'가 입력으로 주어질 때 마다 그 승객이 앉은 자리를 출력한다.

예제 입력

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

예제 출력 2

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

예제 출력 3

1 1
10 2
5 2
7 1
4 2
2 2
4 1

힌트