ŠKOLSKO NATJECANJE 2013. / Srednja škola, I. podskupina (1. i 2. razred) - 3. zadatak

Mirko je zaljubljenik u društvene mreže i za svaku od njih ima istu zaporku koju često mijenja.

Iako se Mirko približno sjeća zaporke koju je zadnji puta koristio prije nekoliko dana, zaboravio je točan oblik i nikako se ne uspijeva prijaviti na sustav.

Treba mu pomoć da pronađe zaporku koja se podudara s pojedinostima tj. uzorcima kojih se sjeća.

Mirkova zaporka je niz od jednog ili više malih slova engleske abecede. Uzorak je niz znakova koji se sastoji od malih slova engleske abecede, zagrada '(', ')' te vertikalne crte '|'.

Uzorak sadrži točno jedan pravilno spareni par zagrada te se unutar tih zagrada nalazi dva ili više (ne nužno različitih) nizova malih slova odvojenih vertikalnim crtama.

Tako su, na primjer '(a|a)', '(mirko|slavko)', i 'm(i|a|ua)rko' ispravni uzorci dok 'mirko', '(mir|)', 'a(b|(a|d))', 'm(i|a|ua)rk(o|a)' nisu.

Uzorak označava nekoliko mogućih zaporki.

Točnije, nizovi unutar zagrada označavaju sve moguće alternative koje se mogu nalaziti na tom mjestu u zaporci.

Tako, na primjer, točno tri zaporke odgovaraju uzorku 'm(i|a|ua)rko', a to su redom 'mirko', 'marko' i 'muarko'.

Napiši program koji će naći zaporku koja odgovara svakom od zadanih uzoraka.

Test podaci će biti takvi da uvijek postoji jedinstveno rješenje.

Ulazni podaci

U prvoj retku ulaza nalazi se prirodni broj N (2 ≤ N ≤ 5) - broj uzoraka.

Svakom od sljedećih N redova nalazi se po jedan uzorak - niz od najviše 100 malih slova engleske abecede i znakova zagrada '(', ')' te vertikalne crte '|' (ASCII kôd 124).

Izlazni podaci

U prvi i jedini red potrebno je ispisati zaporku koja odgovara svakom od uzoraka.

Primjeri test podataka

Ulaz

2
m(i|a)rko
mirk(a|o)

Izlaz

mirko

Ulaz

3
(mirko|slavko|janko)
(mir|slav|jan)ko
(m|s|j|sl)anko

Izlaz

janko