NIKO

시간 제한1초메모리 제한256 MB

요약

제시된 O-V-N 포메이션마다 후보 선수 중 10명을 각자 가능한 라인에 배치할 수 있는지 판단합니다.

난이도: 보통10점 중 4점
유형: 그래프
정답자: 아직 제출이 없습니다

문제

2018년 러시아. 이제 젊다고 하기는 어려운 감독 니코가 대표팀을 이끌고 브라질과 맞붙는다.

경기를 준비할 때 가장 먼저 하는 일은 포메이션을 정하는 것이다. 포메이션은 세 정수 $O$ , $V$ , $N$ 으로 나타낸다. $O$ 는 수비 인원, $V$ 는 미드필드 인원, $N$ 은 공격 인원이고 항상 $O + V + N = 10$ 이다.

포메이션을 정한 다음에는 선수를 신중하게 골라야 한다. 모든 선수가 수비의 달인이거나 세계적인 골잡이는 아니다. 니코는 자기 선수를 잘 알고 있어서 각 선수가 어느 라인을 소화하는지 안다. 소화하지 못하는 라인에 선수를 세우는 것은 전술적 자살이다.

니코와 코치진은 브라질을 상대로 고려해 볼 포메이션 목록까지는 만들었지만, 그중 어떤 포메이션을 지금 있는 선수로 실제로 꾸릴 수 있는지는 따져 보지 못했다. 대신 판단해 주자.

입력

첫째 줄에 고려 중인 포메이션의 수 $F$ ( $1 \le F \le 10$ )가 주어진다.

다음 $F$ 개의 줄에 포메이션이 한 줄에 하나씩 O-V-N 형식으로 주어진다. 세 수는 $0 \le O, V, N \le 10$ 을 만족하고 $O + V + N = 10$ 이다.

다음 줄에 대표팀에 들어오려는 선수의 수 $M$ ( $10 \le M \le 22$ )이 주어진다.

다음 $M$ 개의 줄에 각 선수가 소화하는 라인이 주어진다. 서로 다른 문자로 이루어진, 비어 있지 않은 문자열이며 O는 수비, V는 미드필드, N은 공격을 뜻한다.

출력

정확히 $F$ 개의 줄을 출력한다. $i$ 번째 줄에는 니코가 가진 선수로 $i$ 번째 포메이션을 꾸릴 수 있으면 DA, 꾸릴 수 없으면 NE를 출력한다.

한 선수는 포메이션에서 최대 한 자리만 맡고, 자기가 소화하는 라인에만 설 수 있다. 남은 선수는 벤치에 앉는다.

힌트

첫 번째 예제에서 니코에게는 수비 선수밖에 없다고 할 만하므로 꾸릴 수 있는 포메이션은 이른바 '버스 세우기'인 10-0-0 하나뿐이다.

두 번째 예제에서 4-4-2는 1, 2, 9, 10번 선수를 수비에, 4, 5, 6, 7번 선수를 미드필드에, 3, 8번 선수를 공격에 세우면 된다. 3-5-2는 4, 9, 10번 선수를 수비에, 1, 2, 5, 6, 7번 선수를 미드필드에, 3, 8번 선수를 공격에 세우면 된다. 4-3-3은 공격을 소화하는 선수가 2명뿐이어서 꾸릴 수 없다.

예제5

예제 1

입력

2
4-4-2
10-0-0
10
O
O
O
O
O
O
O
O
ON
NO

예상 출력

NE
DA

예제 2

입력

3
4-4-2
3-5-2
4-3-3
11
OV
OV
OVN
OV
OV
V
V
N
O
O
O

예상 출력

DA
DA
NE

예제 3

입력

10
10-0-0
0-10-0
0-0-10
4-4-2
3-5-2
4-3-3
5-3-2
1-8-1
2-2-6
0-5-5
10
OVN
OVN
OVN
OVN
OVN
OVN
OVN
OVN
OVN
OVN

예상 출력

DA
DA
DA
DA
DA
DA
DA
DA
DA
DA

예제 4

입력

3
4-4-2
5-5-0
0-5-5
10
OV
OV
OV
OV
OV
N
N
N
N
N

예상 출력

NE
NE
DA

예제 5

입력

4
3-4-3
4-3-3
3-3-4
2-5-3
10
O
O
O
V
V
V
V
N
N
N

예상 출력

DA
NE
NE
NE