题目描述
有一张 n×m 的矩形棋盘,左上角格子为 (1,1),右下角格子为 (n,m)。
对于棋盘上的一个格子 (x,y),定义 F(x,y) 表示从 (1,1) 按照国际象棋中马的移动规则走到 (x,y) 的最小步数。
有 T 次询问,每次给出棋盘上的一个子矩形,求这个子矩形中所有格子的 F 之和。
输入格式
第一行三个正整数 T,n,m。
接下来 T 行,每行包含四个正整数 xl,xr,yl,yr,表示该次询问的子矩形的 x 坐标范围为 [xl,xr],y 坐标范围为 yl,yr。
输出格式
对于每组数据,输出一行一个整数,表示答案对 109+7 取模的结果。
样例输入
3 10 10
3 4 5 6
5 5 7 8
3 10 3 10
样例输出
12
9
288
数据范围
对于所有数据,1≤T≤105,3≤n,m≤1018,3≤xl≤xr≤n,3≤yl≤yr≤m。
| 测试点编号 |
n,m≤ |
特殊性质 |
| 1,2 |
5000 |
无 |
| 3,4 |
109 |
保证 xl=xr,yl=yr |
| 5,6 |
保证 2xl>yr,2yl>xr |
| 7,8 |
无 |
| 9,10 |
1018 |