Christmas in Vikendi

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

All the $N$ shops had decided to sell Christmas trees of different heights. Also, one particular shop would only sell trees of a particular height. There were $M$ citizens in the city. As the city of Vikendi is very ancient, its society was divided into many classes. All of the $M$ citizens belong to different and unique classes numbered from $1$ to $M$. 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 $N$ heights of Christmas trees that are sold at $N$ different shops in Vikendi, class level of $M$ different citizens and the range of shops that he/she are allowed to go and finally the sequence of $M$ 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(1 \leq T \leq 10)$ - the number of test cases.

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

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

The next line will contain one integer $M(1 \leq M \leq 10^5)$ - the number of citizens in the city. The following $M$ lines will contain three integers $p, l, \text{ and } r$ where $p(1 \leq p \leq M)$ represents the class level of the citizen and $l$ and $r$ 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 $M$ integers. The$i$-th of them denotes the class level of the citizen that resides in the $i$-th house. All the houses are organized from left to right.

Output

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

Samples

Input	Output
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

Input	Output
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.