给定一个长度为 $n$ 的正整数序列 $a_1,a_2,…,a_n$。
如果将该序列从小到大排序，则可以得到另一个长度为 $n$ 的正整数序列 $b_1,b_2,…,b_n$。
现在，请你回答 $m$ 个询问，询问共分为以下两种：
1 l r，请你计算并输出 $\sum\limits_{i=l}^ra_i$。2 l r，请你计算并输出 $\sum\limits_{i=l}^rb_i$。
输入格式
第一行包含整数 $n$。
第二行包含 $n$ 个正整数 $a_1,a_2,…,a_n$。
第三行包含整数 $m$。
接下来 $m$ 行，每行包含一个询问，格式如题面描述。
输出格式
共 $m$ 行，每个询问输出一行答案。
数据范围
前 $3$ 个测试点满足 $1 \le n,m \le 10$。
所有测试点满足 $1 \le n,m \le 10^5$，$1 \le a_i \le 10^9$，$1 \le l \le r \le n$。
输入样例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
输入样例3：
4
2 2 3 6
9
2 2 3
1 1 3
2 2 3
2 2 3
2 2 2
1 1 3
1 1 3
2 1 4
1 1 2
输出样例3：
5
7
5
5
2
7
7
13
4