Алиса Селезнёва, как и любая другая школьница конца 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 цифр заданного выражения.