The Cartesian coordinate system is set in the sky. There you can see n stars, the i-th has coordinates , a maximum brightness c, equal for all stars, and an initial brightness .

Over time the stars twinkle. At moment 0 the i-th star has brightness . Let at moment t a star has brightness x. Then at moment (t + 1) this star will have brightness x + 1, if , and 0 otherwise.
You want to look at the sky q times. In the i-th time you will look at the moment and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates and the upper right — . For each view, you want to know the total brightness of the stars lying in the viewed rectangle.

A star lies in a rectangle if it lies on its border or lies strictly inside it.

The first line contains three integers n, q, c — the number of the stars, the number of the views and the maximum brightness of the stars.
The next n lines contain the stars description. The i-th from these lines contains three integers — the coordinates of i-th star and its initial brightness.
The next q lines contain the views description. The i-th from these lines contains five integers  — the moment of the i-th view and the coordinates of the viewed rectangle.

For all coordinates, 

For each view print the total brightness of the viewed stars.

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

3
3
5