Święta tuż tuż! Podczas gdy większość miejsc pracy bierze udział w wymianie prezentów typu „Secret Santa”, w Twoim miejscu pracy knuty jest bardziej złowrogi plan: odkrycie sekretów Świętego Mikołaja.

Mikołaj posiada listę grzecznych i niegrzecznych dzieci dla każdego człowieka na Ziemi. Ponieważ jej zawartość jest bardzo poufna, lista została napisana w języku północnopolskim, tajemniczym języku z $N$ literami. Dla większego bezpieczeństwa Mikołaj zaszyfrował tę listę szyfrem podstawieniowym: permutacją $H$ liczb $1, 2, \dots, N$, która przypisuje każdą literę północnopolską $i$ do unikalnej litery $H(i)$. W takim szyfrze żadne dwie litery nie są przypisane do tej samej litery docelowej — formalnie, jeśli $i \neq j$, to $H(i) \neq H(j)$ — ponieważ w przeciwnym razie Mikołaj nie byłby w stanie odczytać swojej listy! (Mikołaj może zdecydować się przypisać niektóre litery do nich samych, $H(i) = i$, żeby było jeszcze trudniej).

Na szczęście dla Ciebie, serwer Mikołaja został słabo zabezpieczony i jest wystawiony na publiczny Internet. Ty i Twoi współpracownicy macie nadzieję włamać się na serwer Mikołaja, odszyfrować jego listę i potwierdzić, że wszyscy jesteście niegrzeczni! (Hakerzy zawsze są niegrzeczni).

Serwer został zbudowany tak, aby Mikołaj mógł szybko sprawdzać swoją listę w biegu. Po połączeniu się z serwerem, użytkownik jest proszony o podanie listy $N$ liczb całkowitych $H(1), H(2), \dots, H(N)$ kodujących permutację $H$, serwer weryfikuje poprawność tej listy, a następnie odszyfrowuje tajną listę Mikołaja. Dzięki miesiącom badań odkryłeś lukę w zabezpieczeniach związaną z czasem odpowiedzi (side-channel timing vulnerability). Załóżmy, że wpisujesz permutację $Q$. Jeśli $H = Q$, serwer natychmiast przyznaje dostęp. W przeciwnym razie rozważ graf o $N$ wierzchołkach i dodaj krawędź z każdego wierzchołka $i$ do wierzchołka $H(Q(i))$. Odkryłeś, że skomplikowany algorytm uwierzytelniania serwera będzie potrzebował dokładnie tyle sekund na odpowiedź komunikatem o błędzie „Access Denied”, ile wynosi liczba spójnych składowych w powstałym grafie.

Na przykład, załóżmy, że $N = 4$, a permutacja szyfrująca $H$ wygląda następująco:

Jeśli spróbujesz zalogować się do serwera z danymi wejściowymi 4 3 2 1, ponieważ ta permutacja nie pasuje do $H$ i ponieważ opisany powyżej graf ma dwie spójne składowe (jedną zawierającą cykl krawędzi $1 \to 4 \to 2 \to 1$ oraz drugą zawierającą tylko pętlę własną $3 \to 3$), serwer odpowie komunikatem o błędzie „Access Denied” po opóźnieniu 2 sekund.

Zauważ, że jeśli spróbujesz zalogować się do serwera wielokrotnie z różnymi danymi wejściowymi $Q$, będzie on uwierzytelniał $Q$ za każdym razem względem tego samego zapisanego $H$. Nie zmienia on $H$ w żaden sposób w odpowiedzi na Twoje dane wejściowe.

Mikołaj zauważy, jeśli jego serwer będzie bombardowany nieautoryzowanymi żądaniami. Oszacowałeś, że możesz wykonać tylko 1 510 prób logowania, zanim wzbudzisz zbyt duże podejrzenia. Czy potrafisz znaleźć skuteczną strategię określenia permutacji szyfrującej?

Interakcja

To jest problem interaktywny. Interakcja rozpoczyna się od wczytania liczby całkowitej $N$ ($1 \le N \le 220$) ze standardowego wejścia, oznaczającej liczbę liter w języku północnopolskim. Sędzia nie jest adaptacyjny: ukryta permutacja $H$ jest wybierana w tym momencie i nie zmieni się przez resztę interakcji.

Aby spróbować zalogować się do serwera, wypisz linię z $N$ oddzielonymi spacjami liczbami całkowitymi $Q(1), \dots, Q(N)$, gdzie $Q$ jest permutacją zbioru $\{1, 2, \dots, N\}$. Następnie wczytaj pojedynczą liczbę całkowitą ze standardowego wejścia, oznaczającą czas w sekundach, jaki zajmuje serwerowi odpowiedź na Twoje dane wejściowe.

Jeśli to opóźnienie wynosi 0, pomyślnie znalazłeś permutację szyfrującą $H$ i Twój program powinien zakończyć działanie. Jeśli nie, to opóźnienie jest liczbą spójnych składowych w grafie zbudowanym zgodnie z opisaną powyżej procedurą.

Możesz spróbować zalogować się co najwyżej 1 510 razy. Jeśli wyczerpiesz liczbę prób, Twój program powinien zakończyć działanie w sposób czysty (choć zostanie oceniony jako błędny za nieodszyfrowanie listy Mikołaja).

Uwagi

Nie zapomnij opróżnić (flush) strumienia wyjściowego po każdej wypisanej linii i zakończyć działanie programu po zakończeniu interakcji. Upewnij się również, że postępujesz dokładnie zgodnie z powyższym protokołem interakcji dotyczącym tego, jakie informacje wypisać w której linii wyjściowej: na przykład, jeśli protokół wymaga wypisania listy liczb całkowitych oddzielonych spacjami w jednej linii, sędzia nie zaakceptuje każdej liczby w osobnej linii.

Jeśli sędzia otrzyma nieprawidłowe lub nieoczekiwane dane wejściowe, wypisze -1, a następnie natychmiast zakończy działanie. Twój program musi to wykryć i zakończyć działanie, aby otrzymać werdykt Wrong Answer. Jeśli Twój program zablokuje się w oczekiwaniu na dalszą interakcję od sędziego lub spróbuje zinterpretować -1 jako liczbę składowych, możesz otrzymać inny werdykt (taki jak Time Limit Exceeded lub Runtime Error) zamiast Wrong Answer.

Otrzymałeś narzędzie wiersza poleceń do lokalnego testowania. Narzędzie to zawiera komentarze na początku wyjaśniające jego użycie.

Przykład