Xiao Z sedang mempelajari sendiri pengetahuan tentang komputer kuantum. Baru-baru ini, ia mempelajari bab komunikasi kuantum dan menemui sebuah masalah menarik. Dalam masalah tersebut, Alice dan Bob sedang melakukan komunikasi kuantum. Bahasa komunikasi mereka adalah sebuah kamus $S$ berukuran $n$. Dalam kamus tersebut, setiap kata $s_i$ ($1 \le i \le n$) dapat dinyatakan sebagai string biner sepanjang $256$ bit. Dalam soal ini, $s_i$ dapat dibuat dengan memanggil fungsi gen, yang dapat dilihat peserta dalam gen.cpp di direktori soal. Parameter fungsi tersebut, $n$, a1, dan a2, diberikan oleh data masukan.
Alice dan Bob akan berkomunikasi sebanyak $m$ kali. Pada setiap komunikasi, Alice mengirimkan tepat satu kata dari kamus kepada Bob. Namun, saluran komunikasi mereka tidak andal dan dapat terganggu derau. Secara khusus, untuk transmisi ke-$i$, misalkan kata asli yang dikirim Alice adalah $x_i$. Derau dapat membalik paling banyak $k_i$ bit pada string biner tersebut. Dengan kata lain, jika string biner yang diterima Bob adalah $y_i$, paling banyak $k_i$ bitnya dapat berbeda dari $x_i$, dan $y_i$ mungkin tidak terdapat dalam kamus $S$.
Sementara itu, Bob mengetahui bahwa si jahat Eve juga menyusup ke saluran komunikasi mereka dan bersiap mengganggu komunikasi. Cara gangguannya adalah mengubah string biner yang diterima Bob menjadi sembarang string biner sepanjang $256$ bit, yang mungkin tidak terdapat dalam kamus $S$. Eve sangat licik dan tidak selalu mengganggu setiap komunikasi.
Sekarang Bob meminta bantuanmu. Untuk setiap komunikasi berikutnya, berdasarkan string biner yang akhirnya diterima Bob dan ambang gangguan derau $k_i$ ($0 \le k_i \le 15$), tentukan apakah mungkin komunikasi tersebut tidak diganggu Eve (yaitu string biner yang diterima Bob dapat diperoleh dengan membalik paling banyak $k_i$ bit dari suatu kata dalam kamus). Jika komunikasi ini mungkin tidak diganggu Eve, keluarkan $1$; jika tidak, keluarkan $0$. Bob sangat memercayai kemampuanmu, sehingga kamu harus menjawab secara daring; persyaratan khususnya dijelaskan pada format masukan.
Untuk mengurangi waktu pembacaan masukan, string yang diterima Bob diberikan sebagai string heksadesimal sepanjang $64$ karakter. String heksadesimal memuat karakter angka 0 sampai 9 serta huruf kapital A sampai F, dengan karakter A sampai F masing-masing menyatakan nilai $10$ sampai $15$.
String heksadesimal dapat diubah menjadi string biner per digit. Misalnya, 5 bersesuaian dengan 0101, A dengan 1010, dan C dengan 1100.
Masukan
Baca data dari berkas qi.in.
Baris pertama masukan berisi empat bilangan bulat nonnegatif $n,m,a_1,a_2$, yang masing-masing menyatakan ukuran kamus, banyaknya komunikasi, serta nilai awal parameter a1 dan a2 pada fungsi gen.
Peserta harus memanggil fungsi gen yang disebutkan dalam deskripsi soal di dalam programnya sendiri untuk membuat daftar kata. Peserta dapat menyalin dan menggunakan kode dalam gen.cpp. Larik Boolean s[N+1][256] dalam program tersebut memuat semua kata.
Berikutnya terdapat $m$ baris, masing-masing berisi sebuah string heksadesimal sepanjang $64$ karakter dan sebuah bilangan bulat nonnegatif $k_i$, yang masing-masing menyatakan string biner yang akhirnya diterima Bob pada komunikasi ke-$i$ dan ambang gangguan derau.
Untuk memaksa peserta menjawab kueri secara daring, setelah memulihkan string biner sepanjang $256$ bit dari string heksadesimal, peserta harus meng-XOR setiap bit string biner tersebut dengan $lastans$ untuk memperoleh string biner sebenarnya yang diterima Bob pada komunikasi ini. Di sini, $lastans \in \{0,1\}$ menyatakan jawaban kueri sebelumnya, dan sebelum kueri pertama, nilai awal $lastans$ adalah $0$.
Perhatian: ketika menggunakan fungsi scanf dan printf untuk membaca atau mengeluarkan variabel bertipe unsigned long long, penentu format yang sesuai adalah llu.
Keluaran
Tulis keluaran ke berkas qi.out.
Keluarkan $m$ baris, masing-masing berisi sebuah bilangan bulat $0$ atau $1$ yang menyatakan jawaban kueri saat ini.
Ilustrasi Kueri
Untuk memudahkan penjelasan soal, kami memberikan contoh keadaan yang disederhanakan dengan menyediakan kata-kata dalam kamus secara langsung, mengurangi panjang kata menjadi $4$, dan mengizinkan kueri dijawab secara luring.
Misalkan ukuran kamus $n=2$, dengan kata-kata 1010 dan 0111.
Untuk kueri B = 1011 dan $k_1=1$, jawabannya seharusnya $1$, yang diperoleh dengan membalik bit keempat dari 1010 (dihitung dari bit tinggi ke bit rendah; hal yang sama berlaku selanjutnya).
Untuk kueri 1 = 0001 dan $k_2=2$, jawabannya seharusnya $1$, yang diperoleh dengan membalik bit kedua dan ketiga dari 0111.
Untuk kueri 1 = 0001 dan $k_3=1$, jawabannya seharusnya $0$.
- Dengan membalik paling banyak $1$ bit dari
1010, kita dapat memperoleh1010,0010,1110,1000, dan1011. - Dengan membalik paling banyak $1$ bit dari
0111, kita dapat memperoleh0111,1111,0011,0101, dan0110. 1 = 0001tidak dapat diperoleh, sehingga string tersebut pasti dihasilkan oleh gangguan Eve.
Contoh
Contoh 1
Lihat qi/qi1.in dan qi/qi1.ans di direktori peserta.
Contoh 2
Lihat qi/qi2.in dan qi/qi2.ans di direktori peserta.
Contoh 3
Lihat qi/qi3.in dan qi/qi3.ans di direktori peserta.
Batasan Kasus Uji
Untuk semua kasus uji: $1 \le n \le 4 \times 10^5$, $1 \le m \le 1.2 \times 10^5$, $0 \le k \le 15$. $a_1$ dan $a_2$ dibuat secara acak seragam dalam $[0,2^{64}-1]$.
| Nomor kasus uji | $n=$ | $m=$ | $k_i \le$ | Sifat khusus |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | $2$ | Tidak ada |
| $2$ | $500$ | $500$ | $15$ | Tidak ada |
| $3$ | $1{,}000$ | $1{,}000$ | $0$ | Tidak ada |
| $4$ | $2{,}000$ | $2{,}000$ | $2$ | Tidak ada |
| $5$ | $5{,}000$ | $5{,}000$ | $15$ | Tidak ada |
| $6$ | $10{,}000$ | $10{,}000$ | $15$ | Tidak ada |
| $7$ | $20{,}000$ | $20{,}000$ | $15$ | Tidak ada |
| $8$ | $100{,}000$ | $100{,}000$ | $1$ | Tidak ada |
| $9$ | $400{,}000$ | $120{,}000$ | $1$ | Tidak ada |
| $10$ | $50{,}000$ | $50{,}000$ | $2$ | Tidak ada |
| $11$ | $70{,}000$ | $70{,}000$ | $3$ | Tidak ada |
| $12$ | $100{,}000$ | $100{,}000$ | $2$ | Tidak ada |
| $13$ | $30{,}000$ | $30{,}000$ | $5$ | Tidak ada |
| $14$ | $60{,}000$ | $60{,}000$ | $4$ | Tidak ada |
| $15$ | $120{,}000$ | $120{,}000$ | $5$ | Tidak ada |
| $16$ | $60{,}000$ | $60{,}000$ | $8$ | Semua string kueri dibuat secara acak |
| $17$ | $120{,}000$ | $120{,}000$ | $12$ | Semua string kueri dibuat secara acak |
| $18$ | $400{,}000$ | $100{,}000$ | $15$ | Semua string kueri dibuat secara acak |
| $19$ | $30{,}000$ | $30{,}000$ | $7$ | Tidak ada |
| $20$ | $60{,}000$ | $60{,}000$ | $9$ | Tidak ada |
| $21$ | $90{,}000$ | $90{,}000$ | $11$ | Tidak ada |
| $22$ | $200{,}000$ | $120{,}000$ | $12$ | Tidak ada |
| $23$ | $400{,}000$ | $80{,}000$ | $15$ | Tidak ada |
| $24$ | $400{,}000$ | $100{,}000$ | $15$ | Tidak ada |
| $25$ | $400{,}000$ | $120{,}000$ | $15$ | Tidak ada |