Summer FLASG Advanced | TelefonulAdvanced

ASG s-a săturat de telefonul lui Nokia cu butoane, așa că s-a dus la un amanet de cartier și și-a luat un Nokia nou. Fiind fan înrăit Fortnite, acesta a vrut să instaleze jocul și pe telefon. A văzut că nu este suportat jocul, însă Flaviu i-a dat un site de unde să descarce o variantă neoficială care merge și pe telefoane mai proaste. A aflat după ce a instalat aplicația că i s-a virusat telefonul și are o mulțime de litere pe ecran. Flaviu a remarcat că unele dintre aceste litere formează cuvinte, așa că i-a înmânat un dicționar $x$ formate din $k$ cuvinte pentru fiecare din cele $Q$ linii de pe ecran.

Cerință

Pentru cele $Q$ linii, să se determine dacă linia curentă se poate forma într-o secvență separată prin spații formată din cuvintele din dicționar.

Date de intrare

Pe prima linie, există numărul natural $Q$.
Pentru fiecare din cele $Q$ interogări se află pe prima linie numerele naturale $n$ care reprezintă lungimea cuvântului $w$ ($|w| = n$), precum și $k$ care reprezintă numărul de cuvinte din dicționar. Pe următoarea linie se află cuvântul $w$. Pe a treia linie se află cuvintele din dicționarul $x$.

Date de ieșire

Pentru fiecare din cele $Q$ interogări, să se afișeze DA dacă se poate forma cuvântul, și NU în caz contrar.

Restricții și precizări

• $1 \leq Q \leq 50$;
• $1 \leq n \leq 300$;
• $1 \leq k \leq 100$;
• $1 \leq |x_k| \leq 20$;
• Atât $w$, cât și $x_i$, conțin doar litere mici ale alfabetului englezesc;
• Toate cuvintele din $x$ sunt unice;
• Cuvintele din dicționar pot fi refolosite într-un cuvânt.

Exemplul 1

stdin

1 
10 12
asgasefort
as ase gas sef se sg efort ef fort ort ga a

stdout

DA

Explicație

Următoarele secvențe pot fi formate:

a sg a se fort
a sg a sef ort
a sg as ef ort
a sg as efort
a sg ase fort
as ga se fort
as ga sef ort
as gas ef ort
as gas efort

Exemplul 2

stdin

1 
13 6
mangoicecream
man go mango ice cream icecream

stdout

DA

Explicație

Se pot genera următoarele cuvinte:

man go ice cream
man go icecream
mango ice cream
mango icecream

Exemplul 3

stdin

1
6 3
masina
ma as ina

stdout

NU

Explicație

Nu există un mod prin care poți împărți masina folosind ma, as si ina.