Detta är ett interaktivt problem.

Du får ett positivt heltal $N$ och en talföljd $S = (S_1, S_2, \ldots, S_N)$ av längd $N$ vars element alla är antingen $0$ eller $1$.

Det finns en riktad bipartit graf $G$ med $N$ hörn numrerade $1, 2, \ldots, N$. Varje hörn i $G$ är färgat: hörnet $v$ är vitt om $S_v = 0$ och svart om $S_v = 1$. Varje riktad kant $(u, v)$ i $G$ uppfyller båda följande villkor:

• $u < v$.
• Hörnen $u$ och $v$ har olika färger.

Domaren håller $G$ dold, och du får inte explicit någon information om dess kanter. Istället får du skicka följande två typer av frågor till domaren, totalt högst $15000$ frågor:

• in $u$ $V$: Fråga domaren om ett svart hörn $u$ och en mängd $V$ av noll eller fler vita hörn. Domaren svarar på huruvida det finns ett hörn $v$ i $V$ sådant att kanten $(v, u)$ existerar.
• out $u$ $V$: Fråga domaren om ett svart hörn $u$ och en mängd $V$ av noll eller fler vita hörn. Domaren svarar på huruvida det finns ett hörn $v$ i $V$ sådant att kanten $(u, v)$ existerar.

Skriv ut vilken som helst av de längsta vägarna i $G$.

Observera att den dolda grafen $G$ är fastställd före interaktionen och förblir oförändrad.

Interaktion

Först ges ett heltal $N$ ($2 \le N \le 500$) från standardindata. Nästa rad innehåller $N$ heltal $S_1, S_2, \ldots, S_N$, vart och ett antingen $0$ eller $1$, åtskilda av mellanslag.

$$ \begin{aligned} &N \\ &S_1 \ S_2 \ \ldots \ S_N \end{aligned} $$

Efter att ha läst indata får du ställa totalt högst $15000$ in-frågor och out-frågor, enligt beskrivningen nedan.

in-fråga

Välj först ett svart hörn $u$ och en mängd $V$ av noll eller fler vita hörn. Konstruera sedan en sträng $T = T_1 T_2 \ldots T_N$ av längd $N$ som endast består av $0$:or och $1$:or så att $T_v$ är $1$ om och endast om $v \in V$. Skriv ut frågan till standardutdata i följande format:

$$ \text{in} \ u \ T $$

Domaren avgör om det finns ett hörn $v$ i $V$ sådant att kanten $(v, u)$ existerar. Låt $r$ vara $1$ om ett sådant hörn finns och $0$ annars. Värdet $r$ ges från standardindata i följande format:

$$ r $$

out-fråga

Välj först ett svart hörn $u$ och en mängd $V$ av noll eller fler vita hörn. Konstruera sedan en sträng $T = T_1 T_2 \ldots T_N$ av längd $N$ som endast består av $0$:or och $1$:or så att $T_v$ är $1$ om och endast om $v \in V$. Skriv ut frågan till standardutdata i följande format:

$$ \text{out} \ u \ T $$

Domaren avgör om det finns ett hörn $v$ i $V$ sådant att kanten $(u, v)$ existerar. Låt $r$ vara $1$ om ett sådant hörn finns och $0$ annars. Värdet $r$ ges från standardindata i följande format:

$$ r $$

När du har bestämt en längsta väg, låt $v_1, v_2, \ldots, v_k$ vara hörnnumren i den ordning de förekommer på vägen, och skriv ut ditt svar till standardutdata i följande format:

$$ ! \ k \ v_1 \ v_2 \ \ldots \ v_k $$

Avsluta ditt program omedelbart efter att du har skrivit ut svaret.

Kommentarer om interaktiv bedömning

Om din utdata inte följer det angivna formatet, eller om ditt program avslutas utan att skriva ut ett svar, är bedömningen odefinierad. Avsluta ditt program omedelbart efter att du har skrivit ut svaret. Annars är bedömningen odefinierad.

Varje gång du skriver ut något, avsluta med en radbrytning och töm bufferten för standardutdata (flush).

Om du ställer fler än $15000$ frågor är bedömningen odefinierad. Observera att utskriften av svaret inte räknas som en fråga.

Exempel

Indata 1

5
1 0 0 1 0

1

1

0

1

Utdata 1

out 1 01101

in 4 01100

in 4 01000

out 4 01001

! 4 1 3 4 5

Anmärkning

I denna exempelinteraktion har den dolda grafen kantmängden $E(G) = \{(1, 2), (1, 3), (1, 5), (3, 4), (4, 5)\}$. Denna information ges inte till programmet.