This problem is a Mooshak version of a SPOJ Problem.

[PC025] 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 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 \(v\) of that tree (there can be more than one tree at the same point). 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 \((x_1, y_1, x_2, y_2)\) which are the coordinates of lower left \((x1, y1)\) and upper right \((x2, y2)\) corner of the rectangular area.

Output

Your program should output \(R\) lines containing the sum of values of the trees which lie inside or on the corresponding rectangular plot.

Constraints

• \( 1 \leq n \leq 10^5 \)
• \( 1 \leq R \leq 5 \cdot 10^4 \)
• \( 0 \leq x,y \lt 10^7 \)
• \( 1 \leq v \lt 10^4 \)
• \( 0 \leq x1 \leq x2 \lt 10^7 \)
• \( 0 \leq y1 \leq y2 \lt 10^7 \)

3
1 1 2
2 2 3
3 3 4
2
1 1 1 2
0 0 5 5

2
9