UPDATE Hey there due to some technical error, there was tle for many submissions. Problem is resolved.

Shani dev, the God of Justice, has a duty to punish those who are sinister, because if you did a wrong deed, result for it should be given, so one day, he got the list of n people, arranged in a row, each one had done some crimes, and thus provided a value for their crimes, in form of a number Ai (which is known as sinCount), now to serve his duty, Shani has to use his powers to punish the people, now if Shani punishes x people, he has to use the power equal to the sum of the sinCount of each individual, also he has to save his power for other reasons too, so he will only punish people from l to r, whose sinCount is greater than or equal to k. For this Shani dev needs your help, he will provide you the number of people, list of the sinCounts of all and Q queries, where each query has 3 integers l, r and k, you have to provide information regarding how much power did he used to punish people from l to r if he punish only those who had their sinCount >= k.

Input First line contains N, the number of people, then next line contains N space separated integers Ai, the sinCount of people, next line contains and integer Q, the number of queries, and next Q lines contain three space separated integers l, r and k (indices are 1 based).

Output For each query you have to output an Integer denoting the power used by Shani dev to punish the sinisters.

Constraints
1 <= n <=100000
1 <= Q <=100000
1 <= Ai <= 1000000000