JOI-kun bersekolah di IOI High School, tempat ujian akhir akan segera diadakan. Dalam ujian tersebut, para siswa akan diuji apakah mereka dapat menghitung nilai sebuah fungsi IOI dengan benar. Fungsi IOI adalah sebuah string yang diperoleh dengan salah satu dari enam aturan berikut yang ditetapkan oleh IOI High School, yang memetakan bilangan bulat antara $1$ dan $10^9$ (inklusif) ke nilai boolean, yaitu True atau False.

1. Misalkan $a$ adalah bilangan bulat antara $1$ dan $10^9$ (inklusif). Maka [a] adalah fungsi IOI (a adalah representasi string dari $a$ dalam notasi desimal). Fungsi IOI ini memetakan bilangan bulat yang lebih besar dari atau sama dengan $a$ ke True, dan bilangan bulat yang lebih kecil dari $a$ ke False.
2. Misalkan f adalah fungsi IOI. Maka (f) juga merupakan fungsi IOI. Fungsi IOI ini memetakan bilangan bulat yang sama ke True dan False seperti f.
3. Misalkan f adalah fungsi IOI. Maka !f juga merupakan fungsi IOI. Fungsi IOI ini memetakan bilangan bulat yang dipetakan oleh f ke True menjadi False, dan sebaliknya.
4. Misalkan f dan g adalah fungsi IOI. Maka f&g juga merupakan fungsi IOI. Fungsi IOI ini memetakan suatu bilangan bulat ke True jika f dan g keduanya memetakannya ke True, dan ke False jika tidak.
5. Misalkan f dan g adalah fungsi IOI. Maka f^g juga merupakan fungsi IOI. Fungsi IOI ini memetakan suatu bilangan bulat ke True jika tepat salah satu dari f atau g memetakannya ke True, dan ke False jika tidak.
6. Misalkan f dan g adalah fungsi IOI. Maka f|g juga merupakan fungsi IOI. Fungsi IOI ini memetakan suatu bilangan bulat ke True jika setidaknya salah satu dari f atau g memetakannya ke True, dan ke False jika tidak.

Jika sebuah fungsi IOI dapat diperoleh menggunakan beberapa aturan, aturan dengan nomor lebih besar menentukan nilai boolean yang menjadi hasil pemetaan bilangan bulat oleh fungsi IOI tersebut. Sebagai contoh, untuk [1]&[2]|[3], aturan 6 diterapkan pada f = [1]&[2] dan g = [3] (bukan menerapkan aturan 4 pada f = [1] dan g = [2]|[3]). Selain itu, untuk aturan 4, 5, dan 6, aturan diterapkan sehingga f menjadi sepanjang mungkin. Sebagai contoh, untuk [4]^[5]^[6], aturan 5 diterapkan pada f = [4]^[5] dan g = [6] (bukan menerapkan aturan 5 pada f = [4] dan g = [5]^[6]).

Untuk mempersiapkan ujian, JOI-kun telah menyiapkan fungsi IOI $S$ dengan panjang $N$ dan bermaksud berlatih menentukan nilai boolean hasil pemetaan $Q$ bilangan bulat $X_1,X_2,\ldots,X_Q$ oleh fungsi IOI ini. Ia meminta bantuan Anda, yang mahir menangani fungsi IOI, untuk membuat contoh solusi.

Tulislah program yang, diberikan $N$, $Q$, $S$, dan $X_1,X_2,\ldots,X_Q$, menentukan nilai boolean hasil pemetaan bilangan bulat $X_1,X_2,\ldots,X_Q$ oleh fungsi IOI $S$.

Masukan

Masukan diberikan melalui masukan standar dalam format berikut:

$$ \begin{array}{ll} N&Q\\ S\\ X_1\\ X_2\\ \vdots\\ X_Q \end{array} $$

Keluaran

Cetak $Q$ baris ke keluaran standar. Baris ke-$i$ ($1\le i\le Q$) harus berisi satu nilai boolean hasil pemetaan bilangan bulat $X_i$ oleh fungsi IOI $S$.

Batasan

• $1\le N\le 1\,000\,000$.
• $1\le Q\le 200\,000$.
• $S$ adalah fungsi IOI dengan panjang $N$.
• $1\le X_i\le 10^9$ ($1\le i\le Q$).
• $N$, $Q$, dan $X_i$ ($1\le i\le Q$) adalah bilangan bulat.

Subsoal

1. (5 poin) $S$ tidak mengandung & atau |.
2. (20 poin) $Q=1$.
3. (10 poin) $N\le 10\,000$.
4. (6 poin) $S$ tidak mengandung ! atau ^.
5. (12 poin) Ketika aturan 4 atau aturan 6 diterapkan dalam proses memperoleh $S$, setidaknya salah satu dari f atau g merupakan fungsi IOI yang diperoleh dari aturan 1.
6. (20 poin) $N\le 400\,000$.
7. (27 poin) Tidak ada batasan tambahan.

Contoh

Masukan 1

15 5
(![2]|[3])&![4]
1
2
3
4
5

Keluaran 1

True
False
True
False
False

Catatan

Untuk beberapa fungsi IOI yang muncul dalam proses memperoleh $S$ menurut aturan pada pernyataan soal, nilai boolean hasil pemetaan bilangan bulat $X_i$ ($1\le i\le Q$) ditunjukkan pada tabel berikut.

Contoh masukan ini memenuhi batasan subsoal 3, 6, dan 7.

Masukan 2

20 4
(!![23])^((([116])))
54
1
200
89

Keluaran 2

True
False
False
True

Catatan

Contoh masukan ini memenuhi batasan subsoal 1, 3, 5, 6, dan 7.

Masukan 3

32 4
[2]|[5]&[1]|(([1000000000])|[7])
4
10
6
1

Keluaran 3

True
True
True
False

Catatan

Contoh masukan ini memenuhi batasan subsoal 3, 4, 6, dan 7.