序列询问

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

给定长度为 $N$ 的整数序列 $a_1,a_2,\ldots,a_N$。每次询问给出长度 $L$。

对于每个位置 $i$，考虑所有长度恰为 $L$ 且包含 $i$ 的连续区间，令 $k_i$ 为这些区间的最大元素和。

对每次询问，输出

$$\bigoplus_{i=1}^{N}\left((i\times k_i)\bmod 2^{64}\right),$$

其中 $\oplus$ 表示按位异或，运算按无符号 $64$ 位整数取模。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

第三行一个整数 $Q$。

接下来 $Q$ 行，每行一个整数 $L$，表示一次询问。

输出格式

对每次询问输出一行一个无符号整数。

样例输入 1

6
10 2 -2 -2 -3 6
4
1
4
2
6

样例输出 1

18446744073709551577
33
18446744073709551609
101

样例输入 2

15
-74 20 19 8 59 -76 96 78 18 93 -16 -44 53 -99 60
10
10
13
2
15
5
8
11
9
3
12

样例输出 2

2956
4085
18446744073709550326
3120
588
3083
1145
2929
18446744073709550560
3771

数据范围

对于所有数据，$1\le N\le 5\times10^4$，$1\le Q\le1024$，$|a_i|\le10^5$，$1\le L\le N$。

子任务编号	分值	特殊限制
1	20	$N\le100$
2	40	$N\le1000$
3		无特殊限制