항공권 조회 게이트의 규칙

문제

항공권 관리 서비스의 보안 게이트는 직원의 역할과 항공권의 노선을 확인하여 요청을 허용하거나 거부한다. 직원 이름이나 항공권 번호 대신 역할 번호와 노선 번호만 판정에 사용한다. 요청에는 조회를 뜻하는 작업 V 또는 변경을 뜻하는 작업 M이 하나 지정된다. 두 작업의 권한은 서로 독립적이므로 조회가 허용된다고 해서 변경도 허용되는 것은 아니다. 보안 규칙 하나는 역할 번호, 노선 번호, 작업, 결과로 이루어진다. 규칙의 역할 번호가 0이면 모든 역할에 적용되며, 양수이면 그 역할에만 적용된다. 노선 번호도 0이면 모든 노선에 적용되며, 양수이면 해당 노선에만 적용된다. 작업에는 와일드카드가 없으며 요청의 작업과 정확히 같아야 한다. 역할 조건, 노선 조건, 작업 조건을 모두 만족하는 규칙만 그 요청에 적용된다. 적용되는 규칙이 여러 개이면 더 구체적인 규칙을 우선한다. 규칙의 구체성은 역할 번호와 노선 번호 중 0이 아닌 값의 개수이다. 따라서 구체성은 0, 1, 2 중 하나이며, 역할만 지정한 규칙과 노선만 지정한 규칙의 구체성은 같다. 적용되는 규칙 중 구체성이 가장 큰 규칙들만 남기고 나머지는 판정에서 제외한다. 규칙의 결과 A는 허용, D는 거부를 뜻한다. 남은 규칙 중 결과가 D인 규칙이 하나라도 있으면 요청을 거부한다. 남은 규칙이 모두 A이면 요청을 허용한다. 처음부터 적용되는 규칙이 하나도 없으면 요청을 거부한다. 같은 조건과 결과를 가진 규칙이 여러 번 입력될 수도 있으며, 반복 횟수는 판정에 영향을 주지 않는다. 규칙은 모든 요청을 처리하는 동안 바뀌지 않는다. 입력에 적힌 규칙 순서나 요청 순서도 우선순위에 영향을 주지 않는다. 각 요청에 대해 위 절차로 결정한 최종 결과를 입력 순서대로 출력하는 프로그램을 작성한다.

입력

첫째 줄에 규칙 수 R과 요청 수 Q가 주어진다. 0 ≤ R ≤ 6,000, 1 ≤ Q ≤ 6,000이다.
다음 R개 줄에 규칙의 역할 번호 U, 노선 번호 F, 작업 O, 결과 E가 주어진다. 0 ≤ U, F ≤ 100,000이고 O는 V 또는 M, E는 A 또는 D이다.
다음 Q개 줄에 요청의 역할 번호 U, 노선 번호 F, 작업 O가 주어진다. 1 ≤ U, F ≤ 100,000이고 O는 V 또는 M이다. 모든 번호는 정수이며 각 줄의 항목은 공백으로 구분된다.

출력

각 요청에 대해 허용이면 A, 거부이면 D를 한 줄에 하나씩 출력한다. 총 Q개 줄을 출력한다.

5 5
0 0 V A
2 0 V D
0 7 V A
2 7 V A
0 0 M D
2 7 V
2 8 V
3 7 V
3 8 M
3 8 V

A
D
A
D
A

4 3
4 0 M A
0 9 M D
4 8 M A
4 8 M D
4 9 M
4 8 M
5 8 V

D
D
D

0 1
1 1 V

D

출처: Devin.KR 자체 제작