캠핑장 구역 출입 규칙

문제

캠핑장에는 1번부터 1,000,000,000번까지 번호가 붙은 야영 구역이 한 줄로 늘어서 있다. 보안 담당자는 구역 번호 구간 단위로 출입 규칙을 내리고, 출입 게이트는 특정 구역에 들어가도 되는지 수시로 물어 온다. 사건은 모두 N개이며 입력에 주어진 순서대로 처리한다. 사건은 세 종류다. 'A l r' 은 l번 이상 r번 이하의 모든 구역을 허용으로 지정하는 규칙이다. 'D l r' 은 같은 방식으로 그 구간을 차단으로 지정하는 규칙이다. 'Q x' 는 그 시점에 x번 구역이 허용 상태인지 묻는 질의다. 규칙의 구간은 서로 겹치거나 포함될 수 있고, 같은 구역에 규칙이 여러 번 내려지면 나중에 내려진 규칙이 앞선 규칙을 덮어쓴다. 즉 어떤 구역의 현재 상태는 그 구역을 포함하는 규칙 가운데 가장 최근에 내려진 규칙(A 또는 D)이 정한다. 지금까지 어떤 규칙에도 포함된 적이 없는 구역은 차단 상태이다. 질의는 그 시점까지 처리된 규칙만 반영해 답한다. 각 질의에 대해 해당 구역이 허용이면 ALLOW, 차단이면 DENY 를 출력한다.

입력

첫 줄에 사건의 수 N 이 주어진다. 이어지는 N 개의 줄에 사건이 하나씩 위 형식으로 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ l ≤ r ≤ 1,000,000,000, 1 ≤ x ≤ 1,000,000,000 이며 모든 값은 정수이다. Q 사건은 하나 이상 존재한다.

출력

Q 사건마다 순서대로 한 줄에 하나씩 ALLOW 또는 DENY 를 출력한다.

8
A 1 10
D 4 6
Q 5
Q 7
A 5 5
Q 5
D 1 100
Q 3

DENY
ALLOW
ALLOW
DENY

3
Q 1000000000
A 1 1000000000
Q 1000000000

DENY
ALLOW

출처: Devin.KR 자체 제작