Piggy是一只可爱的小猪，它正在学习数学。现在，它有一个长度为 n 的正整数序列 a_1, a_2, \cdots, a_n，如果将该序列从小到大排序，可以得到另一个长度为n的正整数序列 b_1, b_2, \cdots, b_n。

Piggy非常喜欢数学，它想测试一下你的数学能力，因此它设计了一个游戏，游戏规则如下：

游戏开始时，Piggy会告诉你 n 和 a_1, a_2, \cdots, a_n，但不会告诉你 b_1, b_2, \cdots, b_n 。

具体来说，你需要回答 m 个询问，每个询问分为以下两种情况：

1、查询区间 [l, r] 内 a_i 的和。

2、查询区间 [l, r] 内 b_i 的和。

在回答完所有询问后，如果你答对了，那么你就能完成这个游戏，并获得Piggy送给你的奖品：一罐美味的巧克力酱！

请你编写一个程序，输入 n 和 a_1, a_2, \cdots, a_n，以及 m 个询问，输出所有询问的答案。

第一行包含整数 n ，表示序列长度。

第二行包含 n 个正整数 a_1, a_2, \cdots, a_n ，表示序列中的元素。

第三行包含整数 m ，表示询问数量。

接下来 m 行，每行包含一个询问，格式如下：

1 l r，表示查询区间 [l, r] 内 a_i 的和；

2 l r，表示查询区间 [l, r] 内 b_i 的和。

输出共 m 行，每行一个整数，表示对应询问的答案。

【数据范围】

前 3 个测试点满足 1 \leq n, m \leq 10 。

所有测试点满足 1 \leq n, m \leq 10^5，1 \leq a_i \leq 10^9，1 \leq l \leq r \leq n。

前缀和