관측 자료 접근 감사

문제

여러 날씨 관측소의 측정 자료를 관리하는 보안 담당자가 접근 요청 기록을 감사한다. 관측소와 사용자는 각각 양의 정수 번호로 구분된다. 감사에 사용하는 규칙은 특정 관측소의 자료를 특정 사용자 또는 모든 사용자에게 허용하거나 거부한다. 각 규칙에는 적용을 시작하는 시각, 적용을 끝내는 시각, 우선순위, 허용 여부가 기록되어 있다. 규칙의 사용자 번호가 0이면 모든 사용자에게 적용되는 공통 규칙이다. 사용자 번호가 양수이면 그 번호의 사용자에게만 적용되는 개인 규칙이다. 규칙은 자신의 관측소 번호가 요청의 관측소 번호와 같고, 요청 시각이 시작 시각 이상이면서 끝 시각 이하일 때 유효하다. 시작 시각과 끝 시각은 모두 적용 범위에 포함되므로, 두 시각이 같은 규칙도 해당 시각에는 유효하다. 접근 여부는 다음 순서로 결정한다. 먼저 해당 요청의 사용자에게 적용되는 유효한 개인 규칙이 하나라도 있는지 확인한다. 있다면 개인 규칙들만 후보로 삼고 모든 공통 규칙을 무시한다. 유효한 개인 규칙이 없다면 해당 관측소의 유효한 공통 규칙들을 후보로 삼는다. 다른 사용자에게만 적용되는 개인 규칙은 후보가 될 수 없다. 후보 중에서는 우선순위 숫자가 가장 큰 규칙을 사용한다. 가장 높은 우선순위의 규칙이 여러 개이고 그중 거부 규칙이 하나라도 있으면 접근을 거부한다. 그 규칙들이 모두 허용 규칙이면 접근을 허용한다. 후보가 하나도 없으면 기본 정책에 따라 접근을 거부한다. 개인 규칙을 후보로 정한 뒤에는 그 결과가 거부이더라도 공통 규칙으로 다시 판정하지 않는다. 입력의 규칙과 요청은 시각순으로 정렬되어 있지 않을 수 있다. 같은 규칙이 여러 번 주어지거나 같은 요청이 반복되어도 각각 유효한 기록이다. 각 접근 요청은 서로 독립적으로 판정하며, 앞선 요청의 결과가 다른 요청이나 규칙을 바꾸지 않는다. 보안 담당자를 위해 모든 요청의 접근 여부를 입력된 요청 순서대로 출력해야 한다.

입력

첫째 줄에 규칙 수 R과 요청 수 Q가 주어진다. 다음 R개 줄에 규칙의 관측소 번호 s, 사용자 번호 u, 시작 시각 l, 끝 시각 r, 우선순위 p, 허용 여부 a가 주어진다. a=0은 거부, a=1은 허용이다. 다음 Q개 줄에 요청의 관측소 번호 s, 사용자 번호 u, 요청 시각 t가 주어진다. 모든 수는 정수이며 0≤R≤11999, 1≤Q≤12000, R+Q≤12000이다. 관측소 번호는 1 이상 1000 이하, 규칙의 사용자 번호는 0 이상 1000 이하, 요청의 사용자 번호는 1 이상 1000 이하이다. 0≤l≤r≤1000000, 0≤t≤1000000, 0≤p≤1000, a∈{0,1}이다.

출력

각 요청에 대해 접근을 허용하면 ALLOW, 거부하면 DENY를 한 줄에 하나씩 출력한다. 반드시 요청이 입력된 순서를 따른다. 적용 가능한 규칙이 없으면 DENY를 출력한다.

5 6
8 0 0 20 90 1
8 3 5 10 1 0
8 3 10 12 2 1
8 3 10 10 2 0
9 0 4 4 7 1
8 3 4
8 3 5
8 3 10
8 3 11
9 2 4
9 2 5

ALLOW
DENY
DENY
ALLOW
ALLOW
DENY

3 5
2 7 6 6 0 1
2 0 0 9 1000 0
2 8 0 9 1000 1
2 7 7
2 7 6
2 8 2
2 9 2
3 8 2

DENY
ALLOW
ALLOW
DENY
DENY

0 2
1 1 0
1000 1000 1000000

DENY
DENY

출처: Devin.KR 자체 제작