지하철 직원 통로의 권한 기록

문제

한 지하철역의 보안 담당자는 직원 전용 통로에서 사용하는 출입증의 접근 권한을 관리한다. 출입증마다 양의 정수 번호가 하나씩 붙어 있으며, 같은 번호는 언제나 같은 출입증을 뜻한다. 이번에 점검할 기록이 시작되는 시점에는 어떤 출입증에도 접근 권한이 없다. 담당자는 시간순으로 정리된 기록을 처음부터 끝까지 처리하면서, 출입 요청이 발생한 순간의 권한 상태를 판정하려 한다. 기록에 등장하지 않은 출입증도 처음에는 권한이 없는 것으로 취급한다. 기록의 종류는 세 가지다. 종류가 1인 기록은 해당 출입증에 접근 권한을 부여한다. 이미 권한이 있는 출입증에 다시 권한을 부여해도 상태는 그대로다. 종류가 2인 기록은 해당 출입증의 접근 권한을 회수한다. 권한이 없는 출입증에서 권한을 회수해도 상태는 그대로다. 종류가 3인 기록은 해당 출입증으로 직원 통로에 들어가려는 요청이다. 요청을 처리하는 시점에 권한이 있으면 ALLOW, 없으면 DENY로 판정한다. 출입 요청 자체는 권한 상태를 바꾸지 않는다. 권한 부여와 회수는 해당 기록을 읽는 즉시 적용되며, 그 뒤에 나오는 모든 기록에 영향을 준다. 같은 출입증에 대한 기록이 여러 번 등장할 수 있고, 서로 다른 출입증의 기록이 섞여 있을 수도 있다. 뒤에 나오는 기록을 보고 앞선 출입 요청의 판정을 바꾸어서는 안 된다. 또한 한 출입증의 권한 변경은 다른 번호의 출입증에 영향을 주지 않는다. 주어진 모든 기록을 순서대로 처리하여 출입 요청의 판정을 출력한다. 출입 요청이 한 번도 등장하지 않는 경우에는 이를 나타내는 NONE을 출력한다.

입력

첫째 줄에 기록의 수 N이 주어진다. 다음 N개 줄에는 기록의 종류 t와 출입증 번호 b가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며 1 ≤ N ≤ 50,000, 1 ≤ t ≤ 3, 1 ≤ b ≤ 100,000이다. 기록은 주어진 순서대로 발생한다.

출력

종류가 3인 기록마다 판정 결과 ALLOW 또는 DENY를 한 줄에 하나씩 발생 순서대로 출력한다. 종류가 3인 기록이 하나도 없으면 NONE을 한 줄에 출력한다.

8
3 17
1 17
3 17
1 17
2 17
3 17
1 28
3 28

DENY
ALLOW
DENY
ALLOW

4
2 6
1 6
1 6
2 6

NONE

5
1 9
1 12
2 9
3 12
3 9

ALLOW
DENY

출처: Devin.KR 자체 제작