栗山未来杀死了很多怪物并获得了很多(即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 位整数类型。