CCOST - Calculate The Cost

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 ≤ 105, r ≤ 50000, 0 ≤ x, y ≤ 107, value of any tree ≤ 104.
For any rectangular area 0 ≤ x1 ≤ x2 ≤ 107, 0 ≤ y1 ≤ y2 ≤ 107
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.


Added by:Ajay Somani
Date:2008-02-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:CodeCraft 08, Problem Setter: Ajay Somani,Anshuman Singh

hide comments
2018-12-21 10:29:19
nai xừ :D
2016-08-18 16:00:37 Phạm Bãng Ðãng
NICE problem :))))
2016-08-09 17:44:29 Himanshu
can be solved with just 1D-BIT.
2015-07-27 11:30:04 anando_du
nice problem ^_^ inclusion exclusion caused me some WA .. and Array Limit caused RTE for 7 times -_- finally AC ^_^
2014-01-09 22:01:36 Rishav Goyal
i think nlogn+rlog^n should pass the time limit. NO?
2013-05-23 14:46:50 aristofanis
int => WA
long long => TLE
^_^

Last edit: 2013-05-23 14:47:12
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.