COCI '14 Contest 6 #2 Niko

View as PDF

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

It is the year 2018, Russia. History repeats itself and the not-so-young football coach Niko is leading the national team in a clash with Brazil.

Choosing a formation is the first step when it comes to preparing the strategy for a football game. A formation can be represented with three integers , and , where denotes the number of defensive players, denotes the number of midfielders and denotes the number of offensive players. It is evident that it must hold .

After choosing a formation, the coach needs to carefully choose the players because not every player is a defensive wizard or a world class striker. The coach knows his players very well. He knows which line suits each player. Setting a player in a line he doesn't know how to play would be tactical suicide.

The coach and his team of expertise have put together a list of formations that can be taken into consideration against Brazil, but in all their expertise they didn't have time to determine the formations which they have suitable players for. Help them!

Input

The first line of input contains the integer , the number of formations taken into consideration.

Each of the following lines contains the formation given as O-V-N. The numbers are positive integers and it holds .

The following line contains the integer , the number of players who want to join the national team.

The of the following lines contains the list of lines that the player can play in. Letter O denotes defense, letter V midfield positions and letter N offense.

Output

Output exactly lines. The line of output should be DA if the coach has suitable players for the formation from the input, or NE if he doesn't.

Sample Input 1

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

Sample Output 1

NE
DA

Explanation for Sample Output 1

We see that Niko has almost only defensive players at his service, so he can only use the formation 10-0-0, the infamous "parking the bus".

Sample Input 2

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

Sample Output 2

DA
DA
NE

Explanation for Sample Output 2

For formation 4-4-2, he can put players 1, 2, 9 and 10 as defense, players 4, 5, 6 and 7 as midfielders, and players 3 and 8 as offense. For formation 3-5-2, he can put players 4, 9 and 10 as defense, players 1, 2, 5, 6 and 7 as midfielders, and players 3 and 8 as offense. Formation 4-3-3 can't be set up because the coach has only 2 offensive players.