Ini adalah soal interaktif. Batasnya adalah $18\,000$ kueri.

Juri memiliki string rahasia yang terdiri dari tepat 1000 digit biner. Pada setiap pengujian soal ini, string ditetapkan sebelumnya dan tidak berubah. Anda harus menemukan string ini menggunakan kueri.

Pada setiap kueri, Anda memilih segmen $[a, b]$ ($1 \le a \le b \le 1000$) untuk ditanyakan. Kemudian juri melempar koin dan memberi Anda salah satu dari dua nilai berikut, masing-masing dengan peluang 50%:

1. Jumlah angka 1 dalam segmen $[a, b]$;
2. Nilai dari $0$ hingga $b - a + 1$ yang tidak sama dengan jumlah angka 1 dalam segmen tersebut, dipilih secara acak seragam.

Anda tidak boleh menggunakan kueri yang sama dua kali. Semua nilai acak dalam soal ini seragam dan saling independen.

Interaksi

Program peserta harus berinteraksi dengan program juri dengan mencetak perintah dalam salah satu format berikut:

• ? a b. Kueri untuk segmen $[a, b]$. Untuk menjawab, program juri mencetak satu bilangan bulat yang, dengan peluang 50%, merupakan jumlah angka 1 dalam segmen $[a, b]$, dan jika tidak, merupakan nilai acak dari $0$ hingga $b - a + 1$ yang berbeda dari jumlah tersebut.
• ! ans. Jawaban soal, dengan ans berupa string sepanjang 1000 yang terdiri dari angka 0 dan 1. Setelah perintah ini, program peserta harus segera berhenti.

Contoh

Masukan 1

2
3
3
1
3

Keluaran 1

? 1 3
? 1 5
? 3 5
? 2 3
? 2 5
! 01101

Catatan

Contoh di atas hanya diberikan untuk menunjukkan format. Dalam contoh ini, panjang string adalah 5. Dalam pengujian pertama yang sebenarnya maupun semua pengujian lainnya, panjang string yang harus ditebak tepat 1000.