| Codeforces Round 415 (Div. 1) |
|---|
| Закончено |
После прекрасного вечера в ресторане пришло время Нуре и Лехе ехать по домам. Хакер, как истинный джентльмен, предложил подвезти девушку к её дому. Нура, конечно же, с удовольствием согласилась. Но вот незадача: Леха никак не может найти свою машину на огромной стоянке близ ресторана. За помощью он решил обратиться к сторожу.
Формально стоянку можно представить как матрицу 109 × 109. Во всех клетках матрицы стоят машины, в каждой клетке - ровно одна машина. У всех машин есть номер, выраженный целым положительным числом. Пронумеруем столбцы и строки матрицы от 1 до 109 слева направо и сверху вниз соответственно. По стечению странных обстоятельств оказалось, что для каждой клетки (x, y) матрицы номер машины, стоящей в этой клетке, равен минимальному числу, которое еще не встречалось среди номеров машин, стоящих на клетках (i, y) и (x, j), 1 ≤ i < x, 1 ≤ j < y.
Левый верхний фрагмент 5 × 5 парковки Леха хочет задать сторожу q запросов, которые помогут хакеру найти свою машину. В каждом запросе Леха дает сторожу пять целых чисел x1, y1, x2, y2, k. После этого сторож должен рассмотреть все клетки (x, y) матрицы, такие что x1 ≤ x ≤ x2 и y1 ≤ y ≤ y2, и если номер машины, стоящей в клетке (x, y), не превышает k, то прибавить этот номер к ответу на запрос. Для каждого запроса Леха просит сказать ему получившуюся сумму. Из-за того, что сумма может получиться достаточно большой, он просит вычислить её по модулю 109 + 7.
Однако сторожу запросы показались невыполнимыми. Помогите бедняге ответить на все запросы Лехи.
В первой строке находится одно целое число q (1 ≤ q ≤ 104) — число запросов, сделанных Лехой.
В следующих q строках задано по пять целых чисел x1, y1, x2, y2, k (1 ≤ x1 ≤ x2 ≤ 109, 1 ≤ y1 ≤ y2 ≤ 109, 1 ≤ k ≤ 2·109) — параметры очередного запроса Лехи.
Выведите q строк — в первой строке ответ на первый запрос, во второй — на второй и так далее.
4
1 1 1 1 1
3 2 5 4 5
1 1 5 5 10000
1 4 2 5 2
1
13
93
0
Разберем подробнее все запросы (в каждом случае запрашиваемая подматрица выделена синим).
В первом запросе (k = 1) Леха спрашивает лишь про верхнюю левую клетку парковки. В ней находится автомобиль с номером 1 и, следовательно, ответ на этот запрос — 1.
Во втором запросе (k = 5) подходящими номерами являются 4, 1, 2, 3, 2, 1, ответом на запрос является 4 + 1 + 2 + 3 + 2 + 1 = 13.
Во третьем запросе (k = 10000) Леха спрашивает про левый верхний фрагмент 5 × 5, при том, что k достаточно велико, поэтому все номера из подматрицы удовлетворяют запросу Лехи, искомая сумма равна 93.
В четвертом запросе (k = 2) ни один из номеров автомобилей не удовлетворяет запросу Лехи, поэтому ответом на него является 0.
