Počet bodov:
Popis:  12b
Program:  8b

V noci len tak ležíš a zrazu počuješ, ako ti do uška šušká ploštička. Jej druhá kamoška ti jemne obkuskáva lakeť. Keďže si programátor a fakt nemáš kamarátov, tak si povieš, že ploštice budú tvoje kamošky. Nezostáva ti nič iné ako ich chytiť do pohára. Ráno sa zobudíš a rozpamätáš sa, že ti tá ploštička niečo hovorila. Majú vlastný jazyk! …alebo to bude len náhoda. Zoberieš si plošticu číslo 2 a začneš počúvať jej slová a zapisovať ich. Z noci si však už len matne spomínaš na to, čo ti hovorila ploštica číslo 1, ale zapíšeš aj tieto slová. Ak úplne nevieš, aké písmenko vyslovila, zapíšeš si všetky, ktoré to mohli byť. Teraz ich už len porovnáš a prídeš na to, či sa jazyky zhodujú. Jednoduché, však?

Úloha

Vašou úlohou je zistiť, či obe ploštice používajú rovnaký jazyk – teda pokúsiť sa zistiť, či slovo, ktoré nám povedala ploštica číslo 2 sa môže zhodovať so slovom, ktoré si pamätáme z noci.

Formát vstupu

Na prvom riadku vstupu dostanete jedno číslo predstavujúce dĺžku slov (\(l\)). Na druhom riadku dostanete jedno číslo – počet dvojíc slov (\(w\)). Za nimi bude nasledovať \(w\) dvojíc riadkov. Na prvom z dvojice riadkov bude jedno slovo, zložené len z veľkých písmen anglickej abecedy. Na druhom riadku z dvojice bude slovo, ktoré si pamätáme z noci. Tieto slová vyzerajú takto: ak som si istý, aké písmenko ploštica povedala, je na tom mieste len písmenko napríklad A. Ak si nie som istý a mohli to byť rôzne písmenká (alebo iba jedno písmenko), sú uzavreté v zátvorkách napríklad (BD).

Formát výstupu

Na výstup vypíšte \(w\) riadkov – na riadku \(i\) vypíšte OK ak sa \(i\)-te slovo, môže zhodovať s \(i\)-tym nekompletným slovom – otázkou. Inak vypíšte NOT OK.

Hodnotenie

Sú 4 sady vstupov, v ktorých platia tieto obmedzenia:

Sada \(1\) \(2\) \(3\) \(4\)
\(1 \le l \le\) \(5\) \(15\) \(15\) \(50\)
\(1 \le w \le\) \(25\) \(50\) \(5\,000\) \(10\,000\)
\(1 \le l\cdot w \le\) \(100\) \(1\,000\) \(50\,000\) \(100\,000\)

Príklady

Input:

1
4
C
(AB)
B
(DB)
B
B
B
D

Output:

NOT OK
OK
OK
NOT OK
  1. Slovo C a slovo (AB), ktoré si pamätáme z noci sa nemôžu zhodovať.
  2. Slovo B a slovo (DB), ktoré si pamätáme z noci sa zhodovať môžu.
  3. Slovo B a slovo B, ktoré si pamätáme z noci sa zhodujú.
  4. Slovo B a slovo D, ktoré si pamätáme z noci sa nemôžu zhodovať.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.