← 返回题目列表

Codeforces · 433/B

B. 栗山未来的石头

中文机器翻译题面 查看原题

栗山未来杀死了很多怪物并获得了很多(即n)块石头。她将石头从 1 编号到 n。第 i 块石头的成本是 vi。 Kuriyama Mirai 想要了解一些关于这些石头的信息,所以她会问你两类问题:

1. 她会告诉你两个数字,l和r (1 ≤ l ≤ r ≤ n),你应该告诉她$$\sum_{i=l}^{r} v_i$$。
2. 设 ui 为第 i 个最便宜石头的成本(如果我们按非递减顺序排列所有石头成本,则该成本将位于第 i 个位置)。这次她会告诉你两个数字,l和r (1 ≤ l ≤ r ≤ n),你应该告诉她$$\sum_{i=l}^{r} u_i$$。

对于每个问题,你都应该给出正确的答案,否则 Kuriyama Mirai 会说“fuyukai desu”,然后变得不高兴。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105)。第二行包含 n 个整数:v1, v2, ..., vn (1 ≤ vi ≤ 109) — 石头的成本。

第三行包含一个整数 m (1 ≤ m ≤ 105) — Kuriyama Mirai 的问题数。然后是m行,每行包含三个整数类型l和r (1 ≤ l ≤ r ≤ n; 1 ≤ type ≤ 2),描述一个问题。如果输入等于 1,那么您应该输出第一个问题的答案,否则您应该输出第二个问题的答案。

输出

打印 m 行。每行必须包含一个整数——这是 Kuriyama Mirai 问题的答案。按照输入的顺序打印问题的答案。

示例

输入 #1

6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6

输出 #1

24
9
28

输入 #2

4
5 5 2 3
10
1 2 4
2 1 4
1 1 1
2 1 4
2 1 2
1 1 1
1 3 3
1 1 3
1 4 4
1 2 2

输出 #2

10
15
5
15
5
5
2
12
3
5

注意

请注意,问题的答案可能会溢出 32 位整数类型。