4. Och, tie darčeky!

Usáma dostal na Vianoce obrovskú kopu darčekov. A to vôbec nepreháňam! Bolo ich tak veľa, že ich ani nestihol začať rozbaľovať. Usáma totiž vie, že rozbaľovať darčeky nemôže len tak. Musí postupovať podľa špeciálneho, ním patentovaného postupu, ktorý je veľmi zložitý na prípravu.

Po skúsenostiach z predchádzajúcich Vianoc si popri práci zhotovil program, ktorý mu vie o každom darčeku celkom dobre predpovedať, koľko radosti získa z jeho otvorenia¹. Podľa svojho programu si svoje darčeky usporiadal do radu s rastúcou predpovedanou radosťou, dokonca mu to tento rok vyšlo tak pekne, že každý darček mal inú predpovedanú radosť a boli to čísla od \(1\) po počet darčekov. Z dĺžky tohto radu sa mu však zamotala hlava a rozhodol sa nechať si otváranie na ďalší deň.

Prišlo vytúžené ráno a Usáma celý naradostený vybehol z postele. Čakalo ho však nemilé prekvapenie. Jeho precízne zostrojený rad bol celý poprehadzovaný. K jeho radu darčekov sa totiž dostala jeho snúbenica Maru a preusporiadala ho podľa kto vie čoho². Rozhodol sa, že namiesto toho, aby darčeky začal otvárať preusporiadané, alebo že by medzi nimi pobehoval ako veverička na káve, zoradí si ich tak, aby sa ich poradie páčilo v každom momente aj Maru. Aby s tým nemal toľko roboty, rozhodol sa, že to celé docieli iba vymieňaním dvojíc darčekov.

Začal teda vymieňať dvojice darčekov a všimol si, že občas mu to Maru dovolí, ale občas ich hneď vymení späť. Po chvíli testovania si všimol, že Maru vadí, ak vymieňa darčeky na na určitých dvojiciach pozícií. Pre každú dvojicu pozícií si teda zistil, či mu Maru dovolí vymeniť darčeky na nej, alebo nie.

Keďže Maru nezaujímajú darčeky, ktoré vymieňa, ale len ich pozície, dá sa ľahko oklamať. Predstavme si, že na pozíciách \(1\), \(2\) a \(3\) sú darčeky A, B a C, čo si môžeme značiť ako (A, B, C). Usáma vie, že môže vymeniť darčeky na pozíciách \((1,2)\), \((2,3)\), ale v žiadnom prípade nemôže vymeniť \((1,3)\). Napriek tomu vie dostať stav (C, B, A), akurát ho to bude stáť viac operácií. Najskôr totiž vymení prvý darček z druhým, potom druhý s tretím (v tomto okamihu vyzerá jeho rad ako (B, C, A)) a opäť prvý z druhým.

Bohužiaľ, napriek tomu sa jeho darčeky nemusia dať zoradiť do pôvodného stúpajúceho poradia. Rád by sa však k tomuto poradiu aspoň čo najviac priblížil. Pokúste sa mu pomôcť.

Úloha

Usáma dostal \(n\) darčekov. Postupnosť čísiel \(1\) až \(n\), kde sa každé číslo nachádza práve raz, nazveme permutácia. Na vstupe dostanete permutáciu \(n\) čísiel, ktorá predstavuje rad v momente keď sa Usáma zobudil. Pre každú dvojicu pozícií sa naviac dozviete, či môžete vymeniť prvky na týchto pozíciách alebo nie.

Vašou úlohou je nájsť najmenšiu permutáciu, ktorú môžete vytvoriť z permutácie na vstupe len výmenou dovolených dvojíc. Permutácia \(A\) je menšia ako permutácia \(B\), ak má na prvej pozícii, kde sa tieto dve permutácie líšia, menšiu hodnotu.

Polovica bodov sa dá získať za riešenie, ktoré predpokladá, že ak sa dajú vymeniť darčeky na daných pozíciách nejakou postupnosťou výmen, tak sa dajú vymeniť aj priamo. Príklad z rozprávky túto vlastnosť nemá, keďže prvky na pozíciach \(1\) a \(3\) sa dajú vymeniť nejakou postupnosťou výmen, ale nie priamo.

 Formát vstupu

Na prvom riadku dostanete číslo \(n\) (\(1 \leq n \leq 1\,000\)) udávajúce počet čísel v permutácii. V druhom riadku bude \(n\) čísel z rozsahu \(1\) až \(n\), každé práve raz, udávajúce počiatočnú permutáciu.

Nasleduje \(n\) riadkov, v každom z nich \(n\) číslic, každá buď 0 alebo 1, s nasledujúcim významom: Ak je v \(i\)-tom riadku a \(j\)-tom stĺpci 1, tak je možné priamo vymeniť darček na pozícii \(i\) s darčekom na pozícii \(j\). Môžete predpokladať, že číslo v \(i\)-tom riadku a \(j\)-tom stĺpci sa zhoduje s číslom v \(j\)-tom riadku a \(i\)-tom stĺpci. Taktiež môžete predpokladať, že v \(i\)-tom riadku a \(i\)-tom stĺpci bude vždy 1.

Formát výstupu

Vypíšte jeden riadok a v ňom \(n\) čísel, najmenšiu permutáciu, korú vie Usáma zostrojiť z pôvodnej, vymieňaním iba povolených dvojíc pozícií.

Hodnotenie

Je päť sád vstupov.

Počet darčekov v týchto sadách je postupne 10, 50, 200, 500, 1000. V prvej, druhej a štvrtej sade navyše platí, že ak sú dve čísla vymeniteľné nejakou postupnosťou výmen, dajú sa vymeniť aj priamo.

Príklady

Input:

3
3 2 1
110
111
011

Output:

1 2 3

Darčeky 3 a 1 nemôže Usáma vymeniť priamo, ale môže ich vymeniť pomocou druhého darčeka.

Input:

3
2 3 1
100
010
001

Output:

2 3 1

Tu si Usáma nijako neporadí, nemôže totiž nič vymieňať.

Input:

4
2 3 1 4
1001
0110
0110
1001

Output:

2 1 3 4