考虑一个由 0 和 1 组成的无限序列 $M$。该序列的第 $k$ 个元素（$k \ge 0$）在 $k$ 的二进制表示中含有奇数个 1 时为 “1”，含有偶数个 1 时为 “0”。

该序列的开头如下：

$$M = 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, \dots$$

我们定义两个序列 $a_1, a_2, \dots, a_m$ 和 $b_1, b_2, \dots, b_m$ 的点积为 $\sum_{i=1}^{m} a_i \cdot b_i$。

给你一个整数数组 $A$。你的任务是对于每个查询 $(x, y, k)$，求序列 $A_x, A_{x+1}, \dots, A_{x+k-1}$ 与 $M_y, M_{y+1}, \dots, M_{y+k-1}$ 的点积。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

第二行包含 $n$ 个整数，表示数组 $A$ 的元素（$1 \le A_i \le 10^4$）。

第三行包含一个整数 $m$，接下来有 $m$ 行，每行包含三个整数 $x$、$y$ 和 $k$，表示你需要回答的查询（$1 \le m \le 10^5$；$1 \le x \le n$；$1 \le k \le n - x + 1$；$0 \le y \le 10^9$）。

输出格式

对于每个查询，在单独的一行中输出一个整数，表示所求的点积值。

样例

输入样例 1

7
1 2 3 4 5 6 7
5
1 1 7
2 100 5
7 2 1
3 4 5
4 3 3

输出样例 1

14
13
7
16
5