아직 계정이 없으신가요? 회원가입

[21년 재직자 대회 예선] 좌석관리
난이도
참가자 수
5
제출 수
17
정답률
33.33%
지원 언어
제한시간 : C/C++/Java/JS/Python(5초)| 메모리 제한 : 1024MB


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

현재 식당에는 좌석 N×M개가 N행 M열로 나열되어 있는데, 각 좌석에는 (1,1)에서 (N,M)로 좌표가 배정되어 있다. x행 y열에 있는 좌석의 좌표는 (x,y)이다.

점심 시간에는 많은 사람들이 식당을 드나든다. 사번이 id인 어떤 사원이 식당에 왔다면, 다음 조건에 맞춰 이 사원을 위한 좌석을 배정해준다.
  • 현재 K개의 좌석이 차 있고, 이 중 i번째 좌석은 (xi,yi)라고 하자. 이 상황에서 어떤 좌석 (X,Y)의 안전도 DX,Y는  이다. 즉, 다른 사람까지의 거리 중 가장 가까운 거리다. 
  • 단, 방역 수칙에 따르면 사람들은 상하좌우에 바로 붙어 앉을 수 없다.


  • 또한 아래의 그림에서 처럼 경계 밖은(좌, 하) 고려하지 않는다. 


  • 기항이는 현재 비어있는 좌석 (X,Y) 중에서 방역 수칙을 고려하는 동시에, 안전도가 가장 높은 좌석을 새로 들어오는 사람에게 배정해준다.
  • 배정해줄수 있는 좌석 중 안전도가 가장 높은 좌석이 여럿 있을 수 있다. 이 때는 그 중에서 X가 가장 낮은 좌석을, X도 같다면 Y가 가장 낮은 좌석을 배정해 준다.
  • 특수하게, 현재 모든 좌석이 비어있다면 (1,1)이 배정된다.

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

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


제약조건
  • 1≤N,M≤20
  • 1≤Q≤3×104
  • 1≤id≤104


입력형식
첫 번째 줄에 세 자연수 N,M,Q가 주어진다.
다음 Q개의 줄에는 각 줄마다 처리해야 하는 작업이 In {id} 혹은 Out {id}의 형태로 주어진다.


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


입력예제1
1 3 10
Out 1
In 1
In 2
In 2
In 3
Out 2
In 3
Out 2
Out 1
In 1


출력예제1
1 didn't eat lunch.
1 gets the seat (1, 1).
2 gets the seat (1, 3).
2 already seated.
There are no more seats.
2 leaves from the seat (1, 3).
3 gets the seat (1, 3).
2 already left seat.
1 leaves from the seat (1, 1).
1 already ate lunch.


입력예제2
4 4 7
In 7
In 6
In 5
In 4
In 3
In 2
In 1


출력예제2
7 gets the seat (1, 1).
6 gets the seat (4, 4).
5 gets the seat (1, 4).
4 gets the seat (4, 1).
3 gets the seat (2, 2).
2 gets the seat (3, 3).
There are no more seats.