Tämä on vuorovaikutteinen tehtävä.

KUPC-kun kirjoitti ohjelman, joka ratkaisee seuraavan tehtävän.

Annetaan puu $T = (V, E)$, jossa on $N$ solmua. Puun $T$ solmujen jonolle $\{a_1, \dots, a_k\}$, jonka pituus on $k$, määritellään pistemäärä seuraavasti. - Olkoon $d(u, v)$ kaarien lukumäärä solmujen $u$ ja $v$ välisellä polulla puussa $T$. Tällöin pistemäärä on $\prod_{i=1}^k d(a_i, a_{(i \bmod k)+1})$.

Annetaan joukon $V$ osajoukko $S$. Etsi jokaiselle $1 \le k \le N$ seuraava arvo $q_k$. - Pistemäärien summa yli kaikkien pituutta $k$ olevien solmujonojen $\{a_1, \dots, a_k\}$, joiden alkiot kuuluvat joukkoon $S$, modulo $2^{61} - 1$.

KUPC-kun pitää puun $T$ tiedot etukäteen salassa ja käyttää jatkuvasti puuta $T$ ohjelmalle annettavana puuna.

Yrität selvittää lehtisolmujen tiedot yllä olevan ohjelman avulla. Kun puun solmujen lukumäärä on $N$, voit esittää seuraavan kysymyksen enintään $N$ kertaa.

• Valitse joukon $V$ osajoukko $S$ ja kysy ohjelman tulostetta.

Olettaen, että KUPC-kunin ohjelma toimii oikein, tunnista kaikki puun $T$ sisältämät lehdet kysymysten avulla saatujen tietojen perusteella.

Tuomari ei ole mukautuva (not adaptive), ja puu $T$ on kiinnitetty ennen vuorovaikutuksen alkua.

Vuorovaikutusprotokolla

Ensin standardisyötteestä annetaan $N$. ($2 \le N \le 50$)

Tulosta jokaiselle kysymykselle standarditulosteeseen seuraavassa muodossa.

? s1s2...sN

Tässä $s_1s_2\cdots s_N$ on pituutta $N$ oleva merkkijono, joka esittää osajoukkoa $S$, missä $s_i = 1$, jos $i \in S$, ja $s_i = 0$, jos $i \notin S$.

Vastauksena standardisyötteestä annetaan seuraava syöte.

q1 q2 ... qN

Kun olet tunnistanut kaikki lehdet, tulosta vastauksesi seuraavassa muodossa.

! t1t2...tN

Tässä $t_1t_2\cdots t_N$ on pituutta $N$ oleva merkkijono, missä $t_i = 1$, jos $i$ on lehti, ja $t_i = 0$, jos se ei ole lehti.

Lopeta ohjelmasi suorituksen välittömästi tämän tulosteen jälkeen.

Aina kun tulostat jotakin, lisää loppuun rivinvaihto ja tyhjennä (flush) standardituloste.

Esimerkki

Esimerkkisyöte 1

5

0 8 0 32 0

0 44 108 968 3960

0 0 0 0 0

0 76 348 3336 22200

Esimerkkituloste 1

? 00101

? 11001

? 10000

? 11111

! 11001

Huomautus

Ensimmäisessä esimerkissä tuomarin salassa pitämän puun kaarijoukko on $(1, 3), (2, 3), (3, 4), (4, 5)$.

Ensimmäisessä kysymyksessä $S = \{3, 5\}$.

Huomaa, että $d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$.

Esimerkiksi on olemassa seuraavat $4$ pituutta $2$ olevaa solmujonoa $a$, joiden alkiot kuuluvat joukkoon $S$.

• Jos $a = (3, 3)$, tämän jonon pistemäärä on $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$.
• Jos $a = (3, 5)$, tämän jonon pistemäärä on $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$.
• Jos $a = (5, 3)$, tämän jonon pistemäärä on $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$.
• Jos $a = (5, 5)$, tämän jonon pistemäärä on $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$.

Tuomari vastaa arvolla $8$ kohdassa $q_2$, mikä on jakojäännös, kun $0 + 4 + 4 + 0$ jaetaan luvulla $2^{61} - 1$.

Laskemalla vastaavasti muille jonojen pituuksille saamme tuomarin vastaukseksi 0 8 0 32 0.

Tämän puun lehdet ovat solmut $1, 2, 5$, ja tulostamalla ! 11001 lehtien tunnistaminen saadaan oikein päätökseen.