题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, . . . , a_n$。 有 $q$ 次询问，其中第 $j (1 ≤ j ≤ q)$ 次询问将会给出 $L_j, R_j (1 ≤ L_j ≤ R_j ≤ n)$。定义区间 $[l, r] (1 ≤ l ≤ r ≤ n)$ 是极好的，当且仅当区间 $[l, r]$ 的长度在 $[L_j, R_j]$ 内，即 $L_j ≤r−l+1 ≤ R_j$。定义区间 $[l, r] (1 ≤ l ≤ r ≤ n)$ 的权值为$\sum_{i=l}^{r}a_i$。对于所有 $i = 1, 2, . . . , n$，求出所有包含$i$ 的极好区间的最大权值，即 $max_{1≤l≤i≤r≤n}\{\sum_{i=l}^{r}a_i| L_j ≤ r−l+ 1 ≤ R_j\}$。

输入

输入的第一行包含一个正整数 $n$，表示序列长度。 输入的第二行包含 $n$ 个整数 $a_1, a_2, . . . , a_n$。 输入的第三行包含一个正整数 $q$，表示询问次数。 输入的第 $j + 3 (1 ≤ j ≤ q)$ 行包含两个正整数 $L_j, R_j$，表示第 $j$ 次询问。

输出

对于每次询问，设包含 $i (1 ≤ i ≤ n)$ 的极好区间的最大权值为 $k_i$，输出一行一个非负整数，表示 $⊕^{n}_{i=1} ((i × k_i) \mod 2^{64})$，其中 $⊕$ 表示二进制按位异或。注意：对于任意整数$x$，存在唯一的非负整数$x′$ 满足 $x′ ≡ x (\mod 2^{64})$ 且 $0 ≤ x′ ≤ 2^{64} − 1$，则记$x \mod 2^{64} = x′$。

输入样例

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

输出样例

18446744073709551603
8
4

提示

【样例 1 解释】 对于第 $1$ 次询问： • 包含 $1$ 的极好区间为 $[1, 1]$ 和 $[1, 2]$，权值分别为 $2, 6$； • 包含 $2$ 的极好区间为 $[1, 2]$，$[2, 2]$ 和 $[2, 3]$，权值分别为 $6, 4, −1$； • 包含 $3$ 的极好区间为 $[2, 3]$，$[3, 3]$ 和 $[3, 4]$，权值分别为 $−1, −5, −4$； • 包含 $4$ 的极好区间为 $[3, 4]$ 和 $[4, 4]$，权值分别为 $−4, 1$。 因此 $k_1 = 6$，$k_2 = 6$，$k_3 = −1$，$k_4 = 1$。 对于第 $2$ 次询问，$k_1 = 2$，$k_2 = 2$，$k_3 = 2$，$k_4 = 2$。 对于第 $3$ 次询问，$k_1 = 6$，$k_2 = 6$，$k_3 = 2$，$k_4 = 2$。 【数据范围】 对于所有测试数据，均有： • $1 ≤ n ≤ 5 × 10^4$，$1 ≤ q ≤ 1, 024$； • 对于所有 $1 ≤ i ≤ n$，均有 $|a_i| ≤ 10^5$； • 对于所有 $1 ≤ j ≤ q$，均有 $1 ≤ L_j ≤ R_j ≤ n$。

测试点编号	n≤	q≤	特殊性质
1	103	1	无
2,3	3,000	50
4	104	128
5	3 × 104	512
6,7	5 ×104	1,024	A
8 ∼ 10		512	B
11,12			C
13		1,024	D
14,15			E
16 ∼ 20			无

特殊性质 A：对于所有 $1 ≤ j ≤ q$，均有 $L_j = R_j$。 特殊性质 B：对于所有 $1 ≤ j ≤ q$，均有 $R_j ≤ 32$。 特殊性质 C：对于所有 $1 ≤ j ≤ q$，均有 $L_j ≤ 16$ 且 $R_j ≥ n − 1000$。 特殊性质 D：对于所有 $1 ≤ j ≤ q$，均有 $L_j > n/2$。 特殊性质 E：对于所有 $1 ≤ j ≤ q$，均有 $L_j > n/4$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共7个测试点，非原站或官方原始数据。总分100分。