A Venn diagram of
~A \operatorname{NOR} B~ from the Wikimedia Commons.
The only required knowledge is the 
~\operatorname{NOR}~ operator. All of its possible outputs can be stored concisely in this table.
 ~a~ |
 ~b~ |
 ~a \operatorname{NOR} b~ |
 ~0~ |
~0~ |
 ~1~ |
| ~0~ |
~1~ |
~0~ |
| ~1~ |
~0~ |
~0~ |
| ~1~ |
~1~ |
~0~ |
You are given a sequence 
~A~ consisting of ~0~'s and ~1~'s. Here, the 
~i^\text{th}~ element of ~A~ is denoted with 
~A_i~. ~A~ has length 
~N~ 
~(2 \le N \le 10^6)~, and is indexed from ~1~ to ~N~.
There are 
~Q~ 
~(1 \le Q \le 10^5)~ queries, with each query consisting of integers 
~x~ and 
~y~ 
~(1 \le x < y \le N)~. For each query, output the value of 
~(A_x \operatorname{NOR} A_{x+1} \operatorname{NOR} \dots \operatorname{NOR} A_{y-1} \operatorname{NOR} A_y)~ by itself on a line. Because the ~\operatorname{NOR}~ operator is not associative, please evaluate the operations from left to right.
Input Specification
The first line contains one integer, ~N~ ~(2 \le N \le 10^6)~.
The second line contains ~N~ space-separated integers. The ~i^\text{th}~ integer is ~A_i~.
The third line contains one integer, ~Q~ ~(1 \le Q \le 10^5)~.
The following ~Q~ lines contain two space-separated integers, ~x~ and ~y~ ~(1 \le x < y \le N)~.
| Subtask |
Points |
Additional Constraints |
| 1 |
20 |
 ~N=2~,  ~Q=1~ |
| 2 |
20 |
 ~N \le 2\,000~,  ~Q \le 2\,000~ |
| 3 |
60 |
No additional constraints. |
Output Specification
For each query, output the result of ~(A_x \operatorname{NOR} A_{x+1} \operatorname{NOR} \dots \operatorname{NOR} A_{y-1} \operatorname{NOR} A_y)~. The operations should be evaluated from left to right.
Sample Input
6
0 1 1 0 0 1
5
1 2
2 6
3 5
4 5
5 6
Sample Output
0
0
1
1
0
Comments
How come when input is 3 5, and the A string is 0 1 1 0 0 1 the output is 1? It should process 1 0 0 which gives a value of 0 when processed with nor?