Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Star sky

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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.

Input

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.

Output

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

Examples

Input

2 3 3

1 1 1

3 2 0

2 1 1 2 2

0 2 1 4 5

5 1 1 5 5

Output

3

0

3

Input

3 4 5

1 1 2

2 3 0

3 3 1

0 1 1 100 100

1 2 2 4 4

2 2 1 4 7

1 50 50 51 51

Output

3

3

5

0

Note

Let's consider the first example.

At the first view, you can see only the first star. At moment 2 its brightness is 3, so the answer is 3.

At the second view, you can see only the second star. At moment 0 its brightness is 0, so the answer is 0.

At the third view, you can see both stars. At moment 5 brightness of the first is 2, and brightness of the second is 1, so the answer is 3.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2018 00:04:34 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|