Mladi haker Žak je odlučio da po svaku cenu dođe do šifre naloga svoga profesora. Otkrio je da je ta šifra tačno jednaka odgovoru na ~Q~ upita nad profesorovim nizom. Profesorov niz ~A_{i}~ ima ~N~ elemenata, a upiti su tipa ~L~ ~R~. Odgovor na upit je vrednost bitovske konjunkcije elemenata niza između indeksa ~L~ i ~R~ (uključujući i njih). Pomozite Žaku da otkrije šifru.

Opis ulaza

U prvom redu nalaze se brojevi ~N~, dužina niza i ~Q~ najveći broj upita nad nizom. U drugom redu nalazi se niz od ~N~ elemenata. U narednih ~Q~ redova nalaze se upiti opisanog formata.

Opis izlaza

Za svaki od ~Q~ upita ispisati vrednost bitovske konjunkcije elemenata između indeksa ~L~ i ~R~.

Primer

Ulaz

5 4
1 5 4 3 2
1 3
4 5
2 5
2 3

Izlaz

0
2
0
4

Objašnjenje primera

Odgovor na prvi upit je: ~1 \ \text{and} \ 5 \ \text{and} \ 4 = 0~. Odgovor na drugi upit je: ~3 \ \text{and} \ 2 = 2~. Odgovor na treći upit je: ~5 \ \text{and} \ 4 \ \text{and} \ 3 \ \text{and} \ 2 = 0~. Odgovor na četvrti upit je: ~5 \ \text{and} \ 4 = 4~.

Ograničenja

• \(1 \leq Q, N \leq 2 \cdot 10^5​\)
• \(0 \leq A_{i} \leq 10^6​\)

Postoje tri podzadatka:

• Podzadatak 1 [15 poena]: \(N, Q \leq 10^3​\).
• Podzadatak 2 [33 poena]: ~A_{i} \leq 1~.
• Podzadatak 3 [52 poena]: Nema dodatnih ograničenja.

Napomena

Operator konjunkcije u Pascal-u je označen sa and, dok u C++ ga zapisujemo pomoću simbola &. Ova operacija \(x\ \text{and} \ y​\) se za nenegativne cele brojeve \(x,y​\) definiše na sledeći način. Prvo se brojevi zapišu u binarnom zapisu. Ukoliko jedan broj ima manje cifara od drugog, dopisuju mu se vodeće nule sve dok ne budu imali isti broj binarnih cifara. Tako se dobijaju dva niza binarnih cifara, označimo ih sa \(a_1, \ldots, a_k​\) i \(b_1, \ldots b_k​\). Zatim se za svaku poziciju \(i \in \{1, \ldots, k \}​\) računa \(c_i​\) pomoću sledećih pravila:

• Za ~a_{i} = 0, b_{i} = 0~ važi ~c_{i} = 0~
• Za ~a_{i} = 0, b_{i} = 1~ važi ~c_{i} = 0~
• Za ~a_{i} = 1, b_{i} = 0~ važi ~c_{i} = 0~
• Za ~a_{i} = 1, b_{i} = 1~ važi ~c_{i} = 1~

Niz binarnih cifara ~c_1, \ldots, c_k~ (koji možda ima vodeće nule) je binarni zapis rezultata, odnosno broja ~x \ \text{and} \ y~.

Bitovska konjunkcija između ~n~ elemenata ~x_{1},x_{2},...,x_{n}~ definiše se kao ~x_{1} \ \text{and} \ x_{2} \ \text{and} \ ... \ \text{and} \ x_{n} = (...(((x_{1} \ \text{and} \ x_{2}) \ \text{and} \ x_{3}) \ \text{and} \ x_{4})...) \ \text{and} \ x_{n}~.