학원 자료실 접근 심사

문제

한 학원의 보안 담당자가 온라인 자료실의 접근 요청을 심사한다. 학원에서는 이용자를 여러 권한 그룹으로 구분하며, 각 접근 요청에는 이용자가 속한 그룹 번호와 열람하려는 자료실 번호가 함께 기록된다. 한 요청에 기록되는 그룹은 정확히 하나다. 담당자는 미리 등록된 규칙 목록만을 사용하여 각 요청을 허용할지 결정해야 한다. 규칙 하나는 그룹 번호 G, 자료실 번호 C, 판정 값 E로 이루어진다. E가 1이면 허용 규칙이고, 0이면 거부 규칙이다. G가 양수인 규칙은 해당 그룹의 요청에만 적용된다. G가 0인 규칙은 공통 규칙으로서 모든 그룹에 적용된다. 어느 경우든 자료실 번호 C는 요청의 자료실 번호와 정확히 같아야 한다. 다른 자료실에 관한 규칙은 판정에 영향을 주지 않는다. 요청을 심사할 때에는 그 요청에 적용되는 규칙을 모두 살펴본다. 그중 거부 규칙이 하나라도 있으면 접근을 거부한다. 거부 규칙이 없고 허용 규칙이 하나 이상 있으면 접근을 허용한다. 적용되는 규칙이 하나도 없는 경우에도 접근을 거부한다. 따라서 특정 그룹의 허용 규칙이 있더라도 같은 자료실의 공통 거부 규칙이 있으면 접근할 수 없다. 공통 허용 규칙과 특정 그룹의 거부 규칙이 함께 적용되는 경우도 마찬가지다. 규칙 목록에는 같은 내용이 여러 번 나타날 수 있으며, 같은 그룹과 자료실에 허용 규칙과 거부 규칙이 모두 등록될 수도 있다. 뒤에 나온 규칙이 앞의 규칙을 덮어쓰는 것은 아니다. 모든 규칙은 동시에 유효하며, 목록에 적힌 순서는 판정과 무관하다. 모든 요청은 주어진 규칙 목록을 그대로 사용하여 독립적으로 심사한다. 요청 처리 중 규칙을 추가하거나 삭제하지 않는다. 보안 담당자를 대신하여 각 요청의 심사 결과를 입력된 순서대로 출력해야 한다.

입력

첫째 줄에 규칙 수 R과 요청 수 Q가 주어진다.
다음 R개 줄에는 규칙을 나타내는 정수 G, C, E가 주어진다.
그다음 Q개 줄에는 요청을 나타내는 정수 G, C가 주어진다.
0 ≤ R ≤ 29,999
1 ≤ Q ≤ 30,000
R + Q ≤ 30,000
규칙의 그룹 번호는 0 ≤ G ≤ 999이며, 요청의 그룹 번호는 1 ≤ G ≤ 999다.
모든 자료실 번호는 1 ≤ C ≤ 999다.
E는 0 또는 1이다.

출력

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

5 5
0 12 1
3 12 0
3 20 1
0 20 0
4 12 1
3 12
4 12
3 20
2 20
2 30

DENY
ALLOW
DENY
DENY
DENY

4 3
5 7 1
5 7 1
5 7 0
8 9 1
5 7
8 9
8 7

DENY
ALLOW
DENY

0 2
1 1
999 999

DENY
DENY

출처: Devin.KR 자체 제작