The Logging Company has been hit with a petition from concerned citizens regarding their uncontrolled tree-cutting. For public relations purposes, they have decided that, moving forward, they will only cut down trees with mass above a certain threshold.

The Logging Company has a line of ~N~ ~(1 \le N \le 100\,000)~ trees. Each tree ~i~ has a mass ~m_i~ ~(1 \le m_i \le 20\,000)~. The Company wants to cut some of the trees, so they've hired you to calculate the mass of all the wood they would get from cutting all the trees with ~m_i~ greater than or equal to ~q~ ~(1 \le q \le 20\,000)~ between positions ~a~ and ~b~ inclusive ~(0 \le a \le b < N)~. In particular, they want you to answer ~Q~ ~(1 \le Q \le 100\,000)~ such queries.

Input Specification

The first line will contain the integer ~N~. For each tree ~i~, the ~i^{th}~ (from 0) integer on the second line will contain the integer mass ~m_i~. The third line will contain the number ~Q~, the number of queries the logging company wants you to answer. The next ~Q~ lines will contain three integers ~a~ and ~b~ and ~q~.

Output Specification

For each query, print the total mass of the trees at position ~i~ such that ~a \le i \le b~, and ~m_i \ge q~.

Sample Input

5
1 3 4 2 5
5
0 4 3
1 3 2
0 4 5
4 4 1
0 4 1

Sample Output

12
9
5
5
15