Interval

题号：NC209992
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Mr. W have a sequence A with length N.

$F(l,r) = A_l\&A_{l+1}\&...\&A_r$

Set $S(l,r) = \{ F(a,b)\ | min(l, r)\leq a \leq b \leq max(l, r) \}$

Mr.W makes Q queries. For each query he wants to know the size of S(L,R) for given L, R.

L, R will not be given directly. He will give you L' and R'.

$L = (L' \oplus lastans) \% N + 1$

$R = (R' \oplus lastans) \% N + 1$

$\oplus$ means XOR.

Lastans donates the answer of last query. It's zero at the beginning.

The first line contains one integer.
Next line contains N integers .
Next line contains one integer 
Next Q lines each contains two integers .

Q lines, the answer of each query.

示例1

复制

5
15 14 13 11 7
3
2 5
2 5
2 5

复制

4
1
3