На небе задана декартова система координат. Там видно 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). Для каждого просмотра вы хотите узнать суммарную яркость звёзд, лежащих в просмотренном прямоугольнике.
Звезда лежит в прямоугольнике, если она лежит на его границе, либо лежит строго внутри него.
Выходные данные
Для каждого просмотра выведите суммарную яркость просмотренных звёзд.
Примечание
Рассмотрим первый пример.
При первом просмотре видно только первую звезду. В момент времени 2 её яркость равна 3, поэтому ответ на этот запрос — 3.
При втором просмотре видно только вторую звезду. В момент времени 0 её яркость равна 0, поэтому ответ на этот запрос — 0.
При третьем просмотре видно обе звезды. В момент времени 5 яркость первой равна 2, а второй — 1, поэтому ответ на этот запрос — 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|