Given an integer sequence $a_1, a_2, \dots, a_n$ of length $n$. There are $q$ queries. For each query $j$ ($1 \le j \le q$), you are given $L_j, R_j$ ($1 \le L_j \le R_j \le n$). An interval $[l, r]$ ($1 \le l \le r \le n$) is called excellent if its length is within $[L_j, R_j]$, i.e., $L_j \le r - l + 1 \le R_j$. The weight of an interval $[l, r]$ is defined as $\sum_{i=l}^r a_i$. For all $i = 1, 2, \dots, n$, find the maximum weight among all excellent intervals containing $i$, i.e., $\max_{1 \le l \le i \le r \le n} \{ \sum_{k=l}^r a_k \mid L_j \le r - l + 1 \le R_j \}$.

Input

Read data from the file query.in. The first line contains a positive integer $n$, representing the length of the sequence. The second line contains $n$ integers $a_1, a_2, \dots, a_n$. The third line contains a positive integer $q$, representing the number of queries. The $j+3$-th line ($1 \le j \le q$) contains two positive integers $L_j, R_j$, representing the $j$-th query.

Output

Output to the file query.out. For each query, let $k_i$ be the maximum weight of an excellent interval containing $i$ ($1 \le i \le n$). Output a single non-negative integer per line, representing $\bigoplus_{i=1}^n ((i \times k_i) \pmod{2^{64}})$, where $\bigoplus$ denotes the bitwise XOR operation. Note: For any integer $x$, there exists a unique non-negative integer $x'$ such that $x' \equiv x \pmod{2^{64}}$ and $0 \le x' \le 2^{64} - 1$, which is denoted as $x \pmod{2^{64}} = x'$.

Examples

Input 1

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

Output 1

18446744073709551603
8
4

Note

For the first query: Excellent intervals containing 1 are $[1, 1]$ and $[1, 2]$, with weights 2 and 6, respectively. Excellent intervals containing 2 are $[1, 2]$, $[2, 2]$ and $[2, 3]$, with weights 6, 4, and $-1$, respectively. Excellent intervals containing 3 are $[2, 3]$, $[3, 3]$ and $[3, 4]$, with weights $-1$, $-5$, and $-4$, respectively. Excellent intervals containing 4 are $[3, 4]$ and $[4, 4]$, with weights $-4$ and 1, respectively. Thus $k_1 = 6$, $k_2 = 6$, $k_3 = -1$, $k_4 = 1$. For the second query, $k_1 = 2$, $k_2 = 2$, $k_3 = 2$, $k_4 = 2$. For the third query, $k_1 = 6$, $k_2 = 6$, $k_3 = 2$, $k_4 = 2$.

Input 2

(See query/query2.in)

Output 2

(See query/query2.ans)

Note

This example satisfies the constraints for test cases 2 and 3.

Input 3

(See query/query3.in)

Output 3

(See query/query3.ans)

Note

This example satisfies the constraints for test case 4.

Input 4

(See query/query4.in)

Output 4

(See query/query4.ans)

Note

This example satisfies the constraints for test cases 6 and 7.

Input 5

(See query/query5.in)

Output 5

(See query/query5.ans)

Note

This example satisfies the constraints for test cases 8 through 10.

Input 6

(See query/query6.in)

Output 6

(See query/query6.ans)

Note

This example satisfies the constraints for test cases 11 and 12.

Input 7

(See query/query7.in)

Output 7

(See query/query7.ans)

Note

This example satisfies the constraints for test case 13.

Input 8

(See query/query8.in)

Output 8

(See query/query8.ans)

Note

This example satisfies the constraints for test cases 16 through 20.

Constraints

For all test data, we have: $1 \le n \le 5 \times 10^4$, $1 \le q \le 1,024$; For all $1 \le i \le n$, $|a_i| \le 10^5$; * For all $1 \le j \le q$, $1 \le L_j \le R_j \le n$.

Special Property A: For all $1 \le j \le q$, $L_j = R_j$. Special Property B: For all $1 \le j \le q$, $R_j \le 32$. Special Property C: For all $1 \le j \le q$, $L_j \le 16$ and $R_j \ge n - 1000$. Special Property D: For all $1 \le j \le q$, $L_j > n/2$. Special Property E: For all $1 \le j \le q$, $L_j > n/4$.