В графическом планировщике есть канва размера n строк на m столбцов. Изначально значение в каждом пикселе равно 0.

Затем к канве применяется k прямоугольных правок. Каждая правка задаётся числами r1, c1, r2, c2, v и означает, что ко всем пикселям прямоугольной области с углами (r1, c1) и (r2, c2) нужно прибавить v.

После применения всех правок поступает q точечных запросов. В каждом запросе задаются координаты пикселя (r, c), и требуется определить его итоговое значение.

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

Первая строка содержит четыре целых числа n, m, k, q — размеры канвы, количество прямоугольных правок и количество запросов.

Каждая из следующих k строк содержит по пять целых чисел r1, c1, r2, c2, v — описание одной прямоугольной правки.

Каждая из следующих q строк содержит по два целых числа r, c — координаты точечного запроса.

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

Для каждого запроса выведите в отдельной строке одно целое число — значение пикселя (r, c) после применения всех прямоугольных правок.

Ограничения

• 1 <= n, m <= 1000
• 1 <= k, q <= 2 * 10^5
• 1 <= r1 <= r2 <= n
• 1 <= c1 <= c2 <= m
• -10^9 <= v <= 10^9
• 1 <= r <= n
• 1 <= c <= m

Примеры

Пример 1

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

1 1 1 3
1 1 1 1 5
1 1
1 1
1 1

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

5
5
5

Пример 2

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

2 3 4 6
1 1 1 1 7
1 2 2 3 -4
2 1 2 2 10
1 1 2 3 1
1 1
1 2
1 3
2 1
2 2
2 3

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

8
-3
-3
11
7
-3