C. Звёздное небо
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На небе задана декартова система координат. Там видно n звёзд, i-я имеет координаты (xi, yi), максимальную яркость c, общую для всех звёзд, и начальную яркость si (0 ≤ si ≤ c).

С течением времени звёзды мерцают. В момент времени 0 i-я звезда имеет яркость, равную начальной si. Пусть в момент времени t какая-то звезда имеет яркость x. Тогда в (t + 1)-й момент времени эта звезда будет иметь яркость x + 1, если x + 1 ≤ c, а иначе у неё будет яркость 0.

Вы хотите q раз посмотреть на небо. В i-й раз вы посмотрите в момент времени ti и увидите прямоугольник, стороны которого параллельны осям координат, левый нижний угол имеет координаты (x1i, y1i), а правый верхний — (x2i, y2i). Для каждого просмотра вы хотите узнать суммарную яркость звёзд, лежащих в просмотренном прямоугольнике.

Звезда лежит в прямоугольнике, если она лежит на его границе, либо лежит строго внутри него.

Входные данные

Первая строка содержит три целых числа n, q, c (1 ≤ n, q ≤ 105, 1 ≤ c ≤ 10) — количество звёзд, количество просмотров неба и максимальная яркость звёзд.

Следующие n строк содержат описание звёзд. i-я из этих строк содержит три целых числа xi, yi, si (1 ≤ xi, yi ≤ 100, 0 ≤ si ≤ c ≤ 10) — координаты i-й звезды и её начальная яркость.

Следующие q строк содержат описание участков неба. i-я из этих строк содержит пять целых чисел ti, x1i, y1i, x2i, y2i (0 ≤ ti ≤ 109, 1 ≤ x1i < x2i ≤ 100, 1 ≤ y1i < y2i ≤ 100) — момент времени i-го просмотра и координаты просмотренного прямоугольника.

Выходные данные

Для каждого просмотра выведите суммарную яркость просмотренных звёзд.

Примеры
Входные данные
2 3 3
1 1 1
3 2 0
2 1 1 2 2
0 2 1 4 5
5 1 1 5 5
Выходные данные
3
0
3
Входные данные
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
Выходные данные
3
3
5
0
Примечание

Рассмотрим первый пример.

При первом просмотре видно только первую звезду. В момент времени 2 её яркость равна 3, поэтому ответ на этот запрос — 3.

При втором просмотре видно только вторую звезду. В момент времени 0 её яркость равна 0, поэтому ответ на этот запрос — 0.

При третьем просмотре видно обе звезды. В момент времени 5 яркость первой равна 2, а второй — 1, поэтому ответ на этот запрос — 3.