1923. [CF 249E]无尽的矩阵

【题目描述】

Alisa Selezneva（译者注：和俄罗斯著名科幻作家季尔·布雷乔夫所著系列儿童科幻小说中的主人公阿丽萨同名，图片出自其小说《一百年以后》改编的电视电影《她来自未来》），像其他21世纪末期的女学生一样，对科学十分感兴趣。她最近参观了MIT（莫斯科时间研究所，Moscow Institute of Time），该研究所的主任，时间机器的发明者之一，Petrov院士，向她讲解了时间机器的构造。

在院士演示时间机器时，Alisa注意到时间机器的速度并不快，她对造成这一缺点的原因十分感兴趣。事实上根据最近的实验，时间机器并没有采用最优算法来解决一个必须解决的问题。如果你找到了一个解决该问题的最佳方法，时间机器的运行速度将会更快，同时能耗更低。

这个未得出最优算法的问题如下：有一个矩阵a，按照以下规则填充：

方格内的数是从1开始的连续正整数。同时，$a[i][j]<a[t][k](i,j,t,k>=1)$，如果：

1.$max(i,j)<max(t,k)$

2.$max(i,j)=max(t,k)$且$j<k$

3.$max(i,j)=max(t,k)$,$j=k$且$i>t$

因此，在最初36个正整数被插入后，矩阵的形态如下：

你必须找出对给定的$x1,y1,x2,y2（x1<=x2,y1<=y2）$快速计算如下表达式的方法：

$\sum\limits_{i=x1}^{x2}\sum\limits_{j=y1}^{y2}a_{i,j}$

由于该表达式的值可能过大，你只需要知道其最后十位数。

但MIT中没人能够解决这个问题。Alisa勇敢地乘坐时间机器旅行到过去，寻求你的帮助。

你需要写一个程序，对于给定的$x1,y1,x2,y2$，找出该表达式的最后十位数。

【输入格式】

第一行一个整数t$（1<=t<=10^5）$，代表数据组数。

接下来t行每行一个数据：四个空格隔开的正整数$x1,y1,x2,y2（1<=x1<=x2<=10^9,1<=y1<=y2<=10^9）$

【输出格式】

对每个询问，若所求值的长度不超过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

【来源】

CODEFORCES 249E