Kuriyama Mirai has killed many monsters and got many (namely n) stones. She numbers the stones from 1 to n. The cost of the i-th stone is vi. Kuriyama Mirai wants to know something about these stones so she will ask you two kinds of questions:

  1. She will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her <image>. 
  2. Let ui be the cost of the i-th cheapest stone (the cost that will be on the i-th place if we arrange all the stone costs in non-decreasing order). This time she will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her <image>. 



For every question you should give the correct answer, or Kuriyama Mirai will say "fuyukai desu" and then become unhappy.

Input

The first line contains an integer n (1 ≤ n ≤ 105). The second line contains n integers: v1, v2, ..., vn (1 ≤ vi ≤ 109) — costs of the stones. 

The third line contains an integer m (1 ≤ m ≤ 105) — the number of Kuriyama Mirai's questions. Then follow m lines, each line contains three integers type, l and r (1 ≤ l ≤ r ≤ n; 1 ≤ type ≤ 2), describing a question. If type equal to 1, then you should output the answer for the first question, else you should output the answer for the second one.

Output

Print m lines. Each line must contain an integer — the answer to Kuriyama Mirai's question. Print the answers to the questions in the order of input.

Examples

Input

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


Output

24
9
28


Input

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


Output

10
15
5
15
5
5
2
12
3
5

Note

Please note that the answers to the questions may overflow 32-bit integer type.
// package Ladder14;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class CF433B {

    static void merge(long arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        long L[] = new long [n1];
        long R[] = new long [n2];

        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    static void sort(long arr[], int l, int r)
    {
        if (l < r)
        {
            // Find the middle point
            int m = (l+r)/2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr , m+1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    public static void main(String[] args) throws IOException {
        Reader s = new Reader();
        int n = s.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextLong();
        }
        StringBuilder ans = new StringBuilder();
        SegmentTree st = new SegmentTree(arr,n);
//        long[] ans1 = new long[n+1];
//        ans1[0] = 0;
////        ans1[1] = arr[0];
//        for (int i = 1; i <= n; i++) {
//            ans1[i] = ans1[i - 1] + arr[i - 1];
//        }
        long[] arr1 = arr.clone();
        sort(arr1,0,n - 1);
        SegmentTree st1 = new SegmentTree(arr1,n);
//        long[] ans2 = new long[n+1];
//        ans2[0] = 0;
//        for (int i = 1; i <= n; i++) {
//            ans2[i] = ans2[i - 1] + arr1[i - 1];
//        }
        int q = s.nextInt();
//        System.out.println(Arrays.toString(ans1));
//        System.out.println(Arrays.toString(ans2));
        for (int i = 0; i < q; i++) {
            int o = s.nextInt();
            int l = s.nextInt() - 1;
            int r = s.nextInt() - 1;
            switch (o){
                case 1 :
//                    ans.append(ans1[r + 1] - ans1[l]);
                    ans.append((long)st.getSum(n,l,r));
                    ans.append("\n");
                    break;
                case 2 :
//                    ans.append(ans2[r + 1] - ans2[l]);
                    ans.append((long)st1.getSum(n,l,r));
                    ans.append("\n");
                    break;
            }
        }
        System.out.println(ans.toString());
    }

    private static class SegmentTree {
        long st[]; // The array that stores segment tree nodes

        /* Constructor to construct segment tree from given array. This
           constructor  allocates memory for segment tree and calls
           constructSTUtil() to  fill the allocated memory */
        SegmentTree(long arr[], int n) {
            // Allocate memory for segment tree
            //Height of segment tree
            int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));

            //Maximum size of segment tree
            int max_size = 2 * (int) Math.pow(2, x) - 1;

            st = new long[max_size]; // Memory allocation

            constructSTUtil(arr, 0, n - 1, 0);
        }

        // A utility function to get the middle index from corner indexes.
        int getMid(int s, int e) {
            return s + (e - s) / 2;
        }

        /*  A recursive function to get the sum of values in given range
            of the array.  The following are parameters for this function.

          st    --> Pointer to segment tree
          si    --> Index of current node in the segment tree. Initially
                    0 is passed as root is always at index 0
          ss & se  --> Starting and ending indexes of the segment represented
                        by current node, i.e., st[si]
          qs & qe  --> Starting and ending indexes of query range */
        long getSumUtil(int ss, int se, int qs, int qe, int si) {
            // If segment of this node is a part of given range, then return
            // the sum of the segment
            if (qs <= ss && qe >= se)
                return (long)st[si];

            // If segment of this node is outside the given range
            if (se < qs || ss > qe)
                return 0;

            // If a part of this segment overlaps with the given range
            int mid = getMid(ss, se);
            return (long)(getSumUtil(ss, mid, qs, qe, 2 * si + 1) +
                    getSumUtil(mid + 1, se, qs, qe, 2 * si + 2));
        }

        /* A recursive function to update the nodes which have the given
           index in their range. The following are parameters
            st, si, ss and se are same as getSumUtil()
            i    --> index of the element to be updated. This index is in
                     input array.
           diff --> Value to be added to all nodes which have i in range */
        void updateValueUtil(int ss, int se, int i, int diff, int si) {
            // Base Case: If the input index lies outside the range of
            // this segment
            if (i < ss || i > se)
                return;

            // If the input index is in range of this node, then update the
            // value of the node and its children
            st[si] = st[si] + diff;
            if (se != ss) {
                int mid = getMid(ss, se);
                updateValueUtil(ss, mid, i, diff, 2 * si + 1);
                updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);
            }
        }

        // The function to update a value in input array and segment tree.
        // It uses updateValueUtil() to update the value in segment tree
        void updateValue(int arr[], int n, int i, int new_val) {
            // Check for erroneous input index
            if (i < 0 || i > n - 1) {
                System.out.println("Invalid Input");
                return;
            }

            // Get the difference between new value and old value
            int diff = new_val - arr[i];

            // Update the value in array
            arr[i] = new_val;

            // Update the values of nodes in segment tree
            updateValueUtil(0, n - 1, i, diff, 0);
        }

        // Return sum of elements in range from index qs (quey start) to
        // qe (query end).  It mainly uses getSumUtil()
        long getSum(int n, int qs, int qe) {
            // Check for erroneous input values
            if (qs < 0 || qe > n - 1 || qs > qe) {
                System.out.println("Invalid Input");
                return -1;
            }
            return getSumUtil(0, n - 1, qs, qe, 0);
        }

        // A recursive function that constructs Segment Tree for array[ss..se].
        // si is index of current node in segment tree st
        long constructSTUtil(long arr[], int ss, int se, int si) {
            // If there is one element in array, store it in current node of
            // segment tree and return
            if (ss == se) {
                st[si] = arr[ss];
                return arr[ss];
            }

            // If there are more than one elements, then recur for left and
            // right subtrees and store the sum of values in this node
            int mid = getMid(ss, se);
            st[si] = constructSTUtil(arr, ss, mid, si * 2 + 1) +
                    constructSTUtil(arr, mid + 1, se, si * 2 + 2);
            return st[si];
        }
    }

}

class Reader
{
    final private int BUFFER_SIZE = 1 << 16;
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;

    public Reader()
    {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public Reader(String file_name) throws IOException
    {
        din = new DataInputStream(new FileInputStream(file_name));
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public String readLine() throws IOException
    {
        byte[] buf = new byte[64]; // line length
        int cnt = 0, c;
        while ((c = read()) != -1)
        {
            if (c == '\n')
                break;
            buf[cnt++] = (byte) c;
        }
        return new String(buf, 0, cnt);
    }

    public int nextInt() throws IOException
    {
        int ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do
        {
            ret = ret * 10 + c - '0';
        }  while ((c = read()) >= '0' && c <= '9');

        if (neg)
            return -ret;
        return ret;
    }

    public long nextLong() throws IOException
    {
        long ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');
        if (neg)
            return -ret;
        return ret;
    }

    public double nextDouble() throws IOException
    {
        double ret = 0, div = 1;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();

        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');

        if (c == '.')
        {
            while ((c = read()) >= '0' && c <= '9')
            {
                ret += (c - '0') / (div *= 10);
            }
        }

        if (neg)
            return -ret;
        return ret;
    }

    private void fillBuffer() throws IOException
    {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        if (bytesRead == -1)
            buffer[0] = -1;
    }

    private byte read() throws IOException
    {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }

    public void close() throws IOException
    {
        if (din == null)
            return;
        din.close();
    }
}

