항공권 조회 차단 구간

문제

항공권 관리 시스템의 보안 담당자는 외부 협력 계정이 조회할 수 있는 항공권을 점검한다. 점검 대상 항공권은 발권 순서대로 1번부터 N번까지 번호가 붙어 있다. 이 계정은 원래 모든 대상 항공권을 조회할 수 있지만, 개인정보 검토가 필요한 항공권에는 별도의 조회 차단 규칙이 적용된다. 하나의 차단 규칙은 두 정수 L과 R로 표현된다. 이 규칙은 번호가 L 이상 R 이하인 모든 항공권의 조회를 차단한다. 양 끝 번호도 차단 대상에 포함된다. 서로 다른 규칙의 구간은 겹칠 수 있으며, 두 규칙의 양 끝 번호가 모두 같을 수도 있다. 같은 구간이 여러 번 등록되었다면 각각을 독립적인 규칙으로 센다. 점검 목록에는 Q개의 항공권 번호가 주어진다. 보안 담당자는 목록의 각 항공권에 대해 조회 허용 여부와 적용되는 차단 규칙의 수를 확인하려 한다. 어떤 항공권을 포함하는 차단 규칙이 하나도 없으면 조회를 허용하고, 하나 이상 있으면 조회를 거부한다. 다른 종류의 허용 규칙이나 예외 규칙은 없으며, 여러 규칙이 겹친다고 해서 차단이 취소되지 않는다. 모든 차단 규칙은 점검을 시작하기 전에 등록되어 있고, 점검 도중에는 추가되거나 삭제되지 않는다. 점검 목록에는 같은 항공권 번호가 여러 번 등장할 수 있다. 이 경우에도 목록에 등장한 순서대로 각각의 판정 결과를 출력해야 한다. 차단 규칙이 전혀 없으면 모든 조회 요청을 허용한다. 주어진 차단 규칙을 바탕으로 점검 목록 전체의 결과를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, M, Q가 공백으로 주어진다. N은 항공권 수, M은 차단 규칙 수, Q는 점검 항목 수다. 1 ≤ N ≤ 200,000, 0 ≤ M ≤ 10,000, 1 ≤ Q ≤ 10,000이다.
다음 M개 줄에 각 규칙의 정수 L, R이 주어진다. 1 ≤ L ≤ R ≤ N이다.
다음 Q개 줄에 점검할 항공권 번호 X가 하나씩 주어진다. 1 ≤ X ≤ N이다.

출력

점검 목록 순서대로 Q개 줄을 출력한다. 적용되는 차단 규칙이 없으면 ALLOW 0을 출력한다. 적용되는 차단 규칙이 C개라면 DENY C를 출력한다. 단어와 정수 사이에는 공백을 하나 출력한다.

8 3 5
2 5
4 7
4 4
1
4
6
8
2

ALLOW 0
DENY 3
DENY 1
ALLOW 0
DENY 1

1 0 2
1
1

ALLOW 0
ALLOW 0

출처: Devin.KR 자체 제작