학원 보관함의 접근 규칙

문제

한 학원은 수업 자료를 전자 보관함에 나누어 저장한다. 보관함은 하나의 최상위 구역에서 시작하며, 각 구역 아래에는 a 구역과 b 구역이 있다. 최상위 구역에서 어떤 순서로 내려갔는지를 문자열로 나타낸 것이 구역 코드다. 예를 들어 aba는 a 구역, 그 아래 b 구역, 다시 그 아래 a 구역으로 내려간 위치를 뜻한다. 최상위 구역 자체는 기호 -로 나타낸다. 보안 담당자는 한 사용자의 접근 권한을 점검하기 위해 N개의 규칙을 등록했다. 각 규칙은 구역 코드와 판정 문자로 이루어진다. 판정 문자 A는 접근 허용, D는 접근 거부를 뜻한다. 어떤 구역에 등록한 규칙은 그 구역 자체와 그 아래의 모든 하위 구역에 적용될 수 있다. 문자열로 표현하면 규칙의 코드가 요청 코드의 접두사일 때 적용될 수 있다는 뜻이다. 최상위 구역의 규칙은 모든 요청에 적용될 수 있다. 하나의 요청에 적용될 수 있는 규칙이 여러 개라면 가장 깊은 구역의 규칙을 선택한다. 즉 최상위 구역을 깊이 0으로 보고, 나머지 코드는 문자열의 길이를 깊이로 보아 깊이가 가장 큰 규칙을 선택한다. 같은 구역 코드로 규칙을 여러 번 등록했다면 입력에서 나중에 나온 규칙 하나만 유효하다. 그러므로 같은 깊이의 유효한 규칙 사이에서 추가로 우선순위를 정할 필요는 없다. 적용될 수 있는 규칙이 하나도 없으면 접근을 거부한다. 상위 구역의 규칙이 접근을 거부하더라도 더 깊은 구역의 규칙이 접근을 허용하면 그 요청은 허용된다. 반대의 경우에도 더 깊은 규칙의 판정을 따른다. 요청한 구역에 규칙이 직접 등록되어 있지 않아도 상위 구역의 유효한 규칙을 사용할 수 있다. 모든 규칙의 등록을 마친 뒤 Q개의 접근 요청이 주어진다. 요청을 처리하는 동안 규칙은 바뀌지 않으며 요청 사이에는 영향을 주고받지 않는다. 각 요청에 대해 위 우선순위에 따라 접근을 허용할지 거부할지 판정하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 Q가 공백으로 구분되어 주어진다. 1 ≤ N, Q ≤ 50,000이다.
다음 N개 줄에 규칙의 구역 코드와 판정 문자 A 또는 D가 공백으로 구분되어 주어진다. 규칙은 입력 순서대로 등록된다.
다음 Q개 줄에 요청 구역 코드가 하나씩 주어진다.
각 구역 코드는 - 또는 길이 1 이상 20 이하인 a, b만으로 이루어진 문자열이다. 규칙과 요청에 등장하는 모든 구역 코드의 길이 합은 150,000 이하이며, -의 길이는 1로 센다.

출력

각 요청의 판정 결과를 입력 순서대로 한 줄에 하나씩 출력한다. 접근을 허용하면 A, 거부하면 D를 출력한다. 적용 가능한 규칙이 없을 때도 D를 출력한다.

5 6
- D
a A
ab D
ab A
aba D
-
b
aa
ab
aba
abb

D
D
A
A
D
A

2 5
ba A
baa D
a
b
ba
baa
bab

D
D
A
D
A

출처: Devin.KR 자체 제작