| Codeforces Round 152 (Div. 1) |
|---|
| Закончено |
Алиса Селезнёва, как и любая другая школьница конца 21 века, интересуется наукой. Недавно она посетила МИВ (Московский Институт Времени), где его глава и один из изобретателей машины времени Академик Петров рассказал ей о том, как устроена машина времени.
Во время демонстрации работы машины времени Алиса заметила, что эта машина не обладает высоким быстродействием и заинтересовалась причиной такого недостатка устройства. Как выяснилось при детальном изучении, одна из задач, решение которой необходимо для работы машины времени, решается не оптимальным алгоритмом. Если найти способ решать такую задачу оптимально, то машина времени будет работать быстрее и расходовать меньше энергии.
Задача, которую не может решить оптимально ни один из сотрудников, заключается в следующем. Существует матрица a, которая заполняется по следующему правилу:
Ячейки заполняются последовательными целыми положительными числами, начиная с единицы. Причем ai, j < at, k (i, j, t, k ≥ 1) если:
- max(i, j) < max(t, k);
- max(i, j) = max(t, k) и j < k;
- max(i, j) = max(t, k), j = k и i > t.
Так, после того, как будут поставлены первые 36 чисел, матрица a примет следующий вид:
Для решения задачи необходимо научиться достаточно быстро находить для заданных значений x1, y1, x2 и y2 (x1 ≤ x2, y1 ≤ y2) значение выражения:
Так как значение этого выражения может быть очень большим, достаточно знать только последние 10 цифр искомого значения.
Итак, никто в МИВ не может решить поставленную задачу. Алиса отважилась воспользоваться машиной времени и отправиться в прошлое, чтобы обратиться за помощью к Вам.
Ваша задача — написать программу, которая по заданными значениям x1, y1, x2 и y2 находит последние 10 цифр заданного выражения.
В первой строке входных данных находится единственное целое число t (1 ≤ t ≤ 105) — количество тестовых наборов, для которых необходимо решить задачу.
Каждая из последующих t строк содержит описание очередного тестового набора — четыре целых положительных числа x1, y1, x2 и y2 (1 ≤ x1 ≤ x2 ≤ 109, 1 ≤ y1 ≤ y2 ≤ 109), разделенных пробелами.
Для каждого из запросов выведите значение выражения, если оно содержит не более 10 знаков. Иначе выведите три символа «.» (без кавычек), а затем десять последних цифр значения выражения. Выводите ответ для каждого запроса на отдельной строке. Как можно более точно придерживайтесь формата, указанного в примере.
5
1 1 1 1
2 2 3 3
2 3 5 6
100 87 288 2002
4 2 5 4
1
24
300
...5679392764
111
