전차 Batch 컴파일 명령

크로아티아의 수도 자그레브에서 새로 운영되는 전차의 좌석은 $1$부터 $N$까지의 자연수 번호가 붙어 있는 $N$개의 행과 $1$과 $2$의 번호가 붙은 2개의 열로 구성된 격자판으로 표현할 수 있습니다. $R_{A}$행 $C_{A}$열에 있는 좌석과 $R_{B}$행 $C_{B}$열에 있는 좌석 간의 거리는 격자의 중심 좌표 사이 유클리드 거리 $\sqrt{ (R_{A} - R_{B})^2 + (C_{A} - C_{B})^2 }$로 정의됩니다.

대부분의 승객들은 대중교통을 이용할 때 혼자 있기를 원하기 때문에, 승객이 앉아 있는 가장 가까운 좌석과의 거리가 가장 먼 좌석에 앉기를 원합니다. 만약 이러한 좌석의 후보가 여러 개 있다면, 행 번호가 작은 좌석을, 그래도 여러 개 있다면 열 번호가 작은 좌석을 고른다고 합니다. 승객이 이렇게 앉고자 하는 좌석을 골라서 그 곳에 앉는다면, 전차에서 내릴 때까지 자리를 옮기지 않습니다. 전차가 비어 있다면, 다음 승객은 무조건 1행 1열의 좌석을 선택할 것입니다.

해야 할 일

승객들이 타고 내린 일련의 과정들이 주어질 때, 각 승객이 앉아 있었던 좌석의 위치를 알아 내는 프로그램을 작성하세요. 초기에 전차는 비어 있습니다.

입력에서는 1 이상 $M$ 이하의 자연수로 번호가 붙여진 $M$개의 이벤트들이 주어집니다. 이벤트에는 두 가지 종류가 있습니다.

• E : 한 승객이 전차 안으로 들어와서 위의 기준에 따라 정한 자리에 앉습니다.
• L : 한 승객이 전차를 빠져나갑니다. 이 이벤트가 주어질 때에는 정수 P도 함께 주어지는데, 이는 하차한 승객이 P번째 이벤트에서 들어온 승객이라는 것을 의미합니다.

승객이 전차에 들어올 때 빈 자리가 최소 하나는 있다는 것이 보장됩니다.

입력

첫 번째 줄에는 전차 좌석의 행의 수 $N$과 이벤트의 수 $M$ ($1 \le N \le 150,000, 1 \le M \le 30,000$)이 공백을 사이로 두고 주어집니다. 다음 $M$개 줄에는 각 이벤트의 정보가 주어집니다. 이 중 $K$번째 줄에는 $K$번 이벤트의 정보가 주어지는데, 주어질 수 있는 경우는 아래 2가지입니다.

• 문자 E
• 문자 L, 공백 하나, 정수 $P_{K}$ ($1 \le P_{K} < K$).
  • $P_{K}$번 이벤트는 그 종류가 E이며, 같은 승객이 두 번 이상 전차를 빠져나가지 않음이 보장됩니다.

출력

출력해야 할 줄 수는 입력에서 주어지는 종류가 E인 이벤트의 수와 같아야 합니다. 각 E 형태의 이벤트에 대해, 입력에서 주어진 순서대로, 승객이 고른 좌석의 행 번호와 열 번호를 한 줄에 하나씩 공백 하나를 사이로 두고 출력해야 합니다.

채점 기준

• 전체 채점 데이터 중 25점에 해당하는 데이터에 대해 $N \le 150, M \le 150.$
• 전체 채점 데이터 중 45점에 해당하는 데이터에 대해 $N \le 1.500, M \le 1,500.$
• 전체 채점 데이터 중 65점에 해당하는 데이터에 대해 $N \le 150,000, M \le 1,500.$

제출 시 피드백

대회 중에 여러분은 답안을 최대 50번까지 제출할 수 있으며, 제출한 답안은 공식 데이터 중 일부로 채점됩니다. 채점이 완료되면 대회 시스템에서 간략한 정보를 찾아볼 수 있습니다.

입출력 예제