Млади хакер Жак је одлучио да по сваку цену дође до шифре налога свога професора. Открио је да је та шифра тачно једнака одговору на \(Q\) упита над професоровим низом. Професоров низ \(A_{i}\) има \(N\) елемената, а упити су типа \(L\) \(R\). Одговор на упит је вредност битовске конјункције елемената низа између индекса \(L\) и \(R\) (укључујући и њих). Помозите Жаку да открије шифру.

Опис улаза

У првом реду налазе се бројеви \(N\), дужина низа и \(Q\) највећи број упита над низом. У другом реду налази се низ од \(N\) елемената. У наредних \(Q\) редова налазе се упити описаног формата.

Опис излаза

За сваки од \(Q\) упита исписати вредност битовске конјункције елемената између индекса \(L\) и \(R\).

Пример

Улаз

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

Излаз

0
2
0
4

Објашњење примера

Одговор на први упит је: \(1 \ \text{and} \ 5 \ \text{and} \ 4 = 0\). Одговор на други упит је: \(3 \ \text{and} \ 2 = 2\). Одговор на трећи упит је: \(5 \ \text{and} \ 4 \ \text{and} \ 3 \ \text{and} \ 2 = 0\). Одговор на четврти упит је: \(5 \ \text{and} \ 4 = 4\).

Ограничења

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

Постоје три подзадатка:

• Подзадатак 1 [15 поена]: \(N, Q \leq 10^3​\).
• Подзадатак 2 [33 поена]: \(A_{i} \leq 1\).
• Подзадатак 3 [52 поена]: Нема додатних ограничења.

Напомена

Оператор конјункције у Pascal-u је означен са and, док у C++ га записујемо помоћу симбола &. Ова операција \(x\ \text{and} \ y​\) се за ненегативне целе бројеве \(x,y​\) дефинише на следећи начин. Прво се бројеви запишу у бинарном запису. Уколико један број има мање цифара од другог, дописују му се водеће нуле све док не буду имали исти број бинарних цифара. Тако се добијају два низа бинарних цифара, означимо их са \(a_1, \ldots, a_k​\) и \(b_1, \ldots b_k​\). Затим се за сваку позицију \(i \in \{1, \ldots, k \}​\) рачуна \(c_i​\) помоћу следећих правила:

• За \(a_{i} = 0, b_{i} = 0\) важи \(c_{i} = 0\)
• За \(a_{i} = 0, b_{i} = 1\) важи \(c_{i} = 0\)
• За \(a_{i} = 1, b_{i} = 0\) важи \(c_{i} = 0\)
• За \(a_{i} = 1, b_{i} = 1\) важи \(c_{i} = 1\)

Низ бинарних цифара \(c_1, \ldots, c_k\) (који можда има водеће нуле) је бинарни запис резултата, односно броја \(x \ \text{and} \ y\).

Битовска конјункција између \(n\) елемената \(x_{1},x_{2},...,x_{n}\) дефинише се као \(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}\).