문제

현대 자동차 그룹에서 사내 식당 매니저로 일하는 현동이는 점심 시간에 맞춰 일을 하고 있다. 오늘 일은 사람들이 사회적 거리두기를 잘 지키면서 식당 좌석에 앉도록 상황을 관리하는 일이다.

현재 식당에는 좌석 개가 행 열로 나열되어 있는데, 각 좌석에는 에서 로 좌표가 배정되어 있다. 행 열에 있는 좌석의 좌표는 이다.

점심 시간에는 많은 사람들이 식당을 드나든다. 사번이 인 어떤 사원이 식당에 왔다면, 다음 조건에 맞춰 이 사원을 위한 좌석을 배정해준다.

• 현재 개의 좌석이 차 있고, 이 중 번째 좌석은 라고 하자. 이 상황에서 어떤 좌석 의 안전도 는 이다. 즉, 다른 사람까지의 거리 중 가장 가까운 거리다.
• 현호는 현재 비어있는 좌석 중에서 안전도가 가장 높은 좌석을 사람에게 배정해준다. 단, 방역 수칙에 따르면 좌석의 상하좌우에 있는 위치에 사람이 있을 때 다른 사람이 앉으면 안되므로 현재 비어있는 좌석 중에서도 상하좌우도 빈 좌석만 배정해줄 수 있다. 좌석 의 상하좌우에 있는 좌석은 , , , 이다.
• 배정해줄 있는 좌석 중 안전도가 가장 높은 좌석이 여럿 있을 수 있다. 이 때는 그 중에서 가 가장 낮은 좌석을, 도 같다면 가 가장 낮은 좌석을 배정해 준다.
• 특수하게, 현재 모든 좌석이 비어있다면 이 배정된다.

사번이 인 어떤 사원이 식당에서 떠난다면, 그 사원이 있던 자리는 빈 자리가 된다.

각 사원들에게 주어지는 점심 식사는 단 한번이므로, 여러 번 점심을 먹을 수는 없다. 그러므로 이미 점심을 먹은 사원은 돌려보내야 한다. 이외에도 각 직원의 점심 식사 여부에 따른 처리가 요구되는데, 출력 형식을 참고하여 모든 작업을 적절히 처리해보자.

입력

첫 번째 줄에 세 자연수 가 주어진다.

다음 개의 줄에는 각 줄마다 처리해야 하는 작업이 In {id} 혹은 Out {id}의 형태로 주어진다.

출력

개의 줄에 걸쳐서, 번째 줄에는 번째 작업을 처리한 결과를 출력한다. 각 작업마다 출력하는 방식은 다음과 같다.

• 작업이 In {id}로 주어졌을 때
  • 사번이 인 사원이 현재 좌석에 앉아 밥을 먹고 있다면, {id} already seated.를 출력한다.
  • 사번이 인 사원이 이미 밥을 먹고 떠났다면, {id} already ate lunch.를 출력한다.
  • 사번이 인 사원이 자리가 가득 차서 좌석을 배정받는 데 실패했다면, There are no more seats.를 출력한다.
  • 사번이 인 사원이 성공적으로 좌석 에 앉았다면, {id} gets the seat ({x}, {y}).를 출력한다.
• 작업이 Out {id}로 주어졌을 때
  • 사번이 인 사원이 아직 점심을 먹지 못했다면, {id} didn't eat lunch.를 출력한다.
  • 사번이 인 사원이 이미 밥을 먹고 좌석을 떠났다면, {id} already left seat.를 출력한다.
  • 사번이 인 사원이 좌석 에 앉아 있었다면, {id} leaves from the seat ({x}, {y}).를 출력한다. 이 사원은 점심을 먹은 상태로 기록된다.