In a small village near the Himalayas, there is a rich land-owner, in possession of a vast, rectangular tract of land. Unknown to him, a major oil corporation has verified the existence of a vast oil resource beneath his land.

The oil company sends a man to negotiate the purchase of a rectangular field from within the landowner's land, with sides parallel to those of his area. The landowner, valuing his land according to the trees growing in it and the area to be purchased, gives the company man a map of his land, marking the location of trees of different types, and a list of the worth of each type of tree.

To ensure the most economic purchase of land with the required dimensions, the company man provides you with the data in his possession, and along with that, a list of the land areas that he considers good by his judgement.

You must provide, for each land area that he has listed, the sum total of the values of the trees that lie within or on the boundary of that land area.

Input

The first line of the input contains an integer T, which is the number of test cases. For each test case, the first line contains an integer n, equal to the number of trees in the area. This line is followed by n lines each containing three integers separated by spaces which are the coordinate of the tree (x, y) and value of that tree. Following this is an integer R, equal to the number of proposals of land areas given by the company man. Next R lines contain 4 integers each (x1, y1, x2, y2) which are the coordinates of lower left (x1, y1) and upper right (x2, y2) corner of the rectangular area.

Output

For each test case, your program should output R lines containing the sum of values of the trees which lie inside or on the corresponding rectangular plot. There should NOT BE any blank lines between output of different test cases.

Example

Input:
1
3
1 1 2
2 2 3
3 3 4
2
1 1 1 2
0 0 5 5

Output:
2
9

Constraints

T ≤ 10, n ≤ 10⁵, r ≤ 50000, 0 ≤ x, y ≤ 10⁷, value of any tree ≤ 10⁴.
For any rectangular area 0 ≤ x1 ≤ x2 ≤ 10⁷, 0 ≤ y1 ≤ y2 ≤ 10⁷
Note 1: There can be more than one tree at the same point.
Note 2: The input data is large (about 15 MB), be careful about your input and output routines.