A11153 | Star sky

The Cartesian coordinate system is set in the sky. There you can see $n$ stars, the $i$ -th has coordinates ( $x_{i}$ , $y_{i}$ ), a maximum brightness $c$ , equal for all stars, and an initial brightness $s_{i}$ ( $0<=s_{i}<=c$ ).

Over time the stars twinkle. At moment $0$ the $i$ -th star has brightness $s_{i}$ . Let at moment $t$ some star has brightness $x$ . Then at moment $(t+1)$ this star will have brightness $x+1$ , if $x+1<=c$ , and $0$ , otherwise.

You want to look at the sky $q$ times. In the $i$ -th time you will look at the moment $t_{i}$ and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates ( $x_{1i}$ , $y_{1i}$ ) and the upper right — ( $x_{2i}$ , $y_{2i}$ ). 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$ ( $1<=n,q<=10^{5}$ , $1<=c<=10$ ) — 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 $x_{i}$ , $y_{i}$ , $s_{i}$ ( $1<=x_{i},y_{i}<=100$ , $0<=s_{i}<=c<=10$ ) — 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 $t_{i}$ , $x_{1i}$ , $y_{1i}$ , $x_{2i}$ , $y_{2i}$ ( $0<=t_{i}<=10^{9}$ , $1<=x_{1i}<x_{2i}<=100$ , $1<=y_{1i}<y_{2i}<=100$ ) — the moment of the $i$ -th view and the coordinates of the viewed rectangle.

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