Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Christmas in Vikendi

By trojan_king · Limits 2s, 512 MB

Once upon a time, there was an ancient city called Vikendi. In the city of Vikendi, there were NN shops. As Christmas was just knocking on the door, all the shops brought Christmas trees to sell.

All the NN shops had decided to sell Christmas trees of different heights. Also, one particular shop would only sell trees of a particular height. There were MM citizens in the city. As the city of Vikendi is very ancient, its society was divided into many classes. All of the MM citizens belong to different and unique classes numbered from 11 to MM. Each citizen was only allowed to go to a particular segment of the market. In that segment, he or she would roam around to different shops and buy the tallest Christmas tree. Once all the citizens bought Christmas trees, they would bring them back and plant them in front of their houses.

In the city of Vikendi, there was only one road and all the houses were situated beside the road. Now, a citizen can be evil. An evil citizen would come out of his/her house and start going right. He/she would steal the Christmas trees from the houses that were situated on the right side of his/her house if and only if the class level of the house owner is lower than himself/herself.

You will be given NN heights of Christmas trees that are sold at NN different shops in Vikendi, class level of MM different citizens and the range of shops that he/she are allowed to go and finally the sequence of MM houses that are situated from left to right sequentially. You need to calculate the sum of total heights of Christmas trees that a citizen will steal considering he/she is evil. Calculate this sum for all the citizens and while doing so for a particular citizen, you can safely assume that he/she is the only evil citizen in the city.

Input

The first line of the input contains one integer T(1T10)T(1 \leq T \leq 10) - the number of test cases.

The first line of each test case contains one integer N(1N105)N(1 \leq N \leq 10^5) - the number of shops in the city.

The next line of each test case will contain NN space separated integers a1,a2,,an(1ai109)a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^9) . The ii-th of them represents the height of the Christmas tree that the ii-th shop sells.

The next line will contain one integer M(1M105)M(1 \leq M \leq 10^5) - the number of citizens in the city. The following MM lines will contain three integers p,l, and rp, l, \text{ and } r where p(1pM)p(1 \leq p \leq M) represents the class level of the citizen and ll and rr represent the range of shops (inclusive) where the citizen is allowed to go.

Finally, the last line of each test case will have a sequence of MM integers. Theii-th of them denotes the class level of the citizen that resides in the ii-th house. All the houses are organized from left to right.

Output

Output MM integers. The ii-th of them will be the sum of the heights of the Christmas trees that the ii-th person would steal considering he/she was evil.

Samples

InputOutput
1
10
1 2 5 8 23 3 10 7 9 100
5
1 5 6
2 1 7
3 4 8
4 7 9
5 6 10
3 4 1 5 2
46 46 0 23 0 
InputOutput
1
10
1 100 2 8 23 3 10 7 9 50
5
1 5 6
2 1 7
3 4 8
4 7 9
5 6 10
3 1 4 5 2
123 0 100 100 0 

Dataset is large, use fast I/O Method.

    Discussion

    Statistics


    81% Solution Ratio

    prodip_bsmrstuEarliest, 1M ago

    prodip_bsmrstuFastest, 0.2s

    Noman_AhmmedLightest, 16 MB

    Zobayer_AbedinShortest, 1244B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.