주차 구역 접근 기록

문제

한 주차장은 차량마다 들어갈 수 있는 구역을 따로 관리한다. 보안 담당자는 관리 시스템에 쌓인 권한 변경 기록을 적용한 뒤, 출입 요청이 허용되는지 판정하려 한다. 차량과 구역은 각각 번호로 구분하며, 같은 차량이라도 구역에 따라 서로 다른 권한을 가진다. 권한 변경 기록 하나는 차량 번호 v, 구역 번호 z, 설정값 a로 이루어진다. 설정값이 1이면 해당 차량의 해당 구역 접근을 허용하고, 0이면 거부한다. 기록은 입력에 주어진 순서대로 적용한다. 같은 차량과 같은 구역에 대한 기록이 여러 번 나타나면 가장 나중에 나온 기록의 설정값만 유효하다. 다른 차량이나 다른 구역에 대한 기록은 이 권한에 영향을 주지 않는다. 어떤 기록도 적용하기 전에는 모든 차량의 모든 구역 접근이 거부된 상태다. 따라서 한 번도 기록에 등장하지 않은 차량과 구역의 조합도 접근을 거부해야 한다. 앞에서 허용된 조합이 뒤에서 거부될 수도 있고, 반대로 거부된 조합이 다시 허용될 수도 있다. 차량 번호가 같다는 이유만으로 그 차량의 모든 구역 접근을 함께 허용해서는 안 된다. 모든 변경 기록을 적용한 뒤 출입 요청을 입력 순서대로 검사한다. 요청 하나에는 차량 번호와 구역 번호가 주어진다. 이때 유효한 설정값이 1이면 ALLOW, 그렇지 않으면 DENY로 판정한다. 출입 요청 자체는 권한을 바꾸지 않으므로 같은 요청이 반복되면 같은 결과를 얻는다. 실제 차량의 이동이나 주차 가능 대수는 고려하지 않는다. 보안 담당자가 확인할 수 있도록 각 요청의 판정 결과를 한 줄씩 출력하는 프로그램을 작성한다. 기록이 하나도 없을 수 있으며, 이 경우에는 모든 요청을 거부한다.

입력

첫째 줄에 권한 변경 기록 수 N과 출입 요청 수 Q가 주어진다. N과 Q는 정수이며 0 ≤ N ≤ 10,000, 1 ≤ Q ≤ 10,000이다.
다음 N개 줄에 정수 v, z, a가 주어진다. 1 ≤ v ≤ 9,999, 1 ≤ z ≤ 9, 0 ≤ a ≤ 1이다.
다음 Q개 줄에 요청할 차량 번호 v와 구역 번호 z가 주어진다. 1 ≤ v ≤ 9,999, 1 ≤ z ≤ 9이다.
변경 기록과 요청은 각각 중복될 수 있다.

출력

각 출입 요청에 대해 접근이 허용되면 ALLOW, 거부되면 DENY를 입력 순서대로 한 줄에 하나씩 출력한다.

5 5
12 2 1
12 3 1
12 2 0
8 2 0
8 2 1
12 2
12 3
8 2
8 3
99 1

DENY
ALLOW
ALLOW
DENY
DENY

0 2
1 1
9999 9

DENY
DENY

출처: Devin.KR 자체 제작