#P17705. [2026年江苏省队集训]矩形

[2026年江苏省队集训]矩形

题目描述

有一张 n×mn\times m 的矩形棋盘,左上角格子为 (1,1)(1,1),右下角格子为 (n,m)(n,m)。

对于棋盘上的一个格子 (x,y)(x,y),定义 F(x,y)F(x,y) 表示从 (1,1)(1,1) 按照国际象棋中马的移动规则走到 (x,y)(x,y) 的最小步数。

有 TT 次询问,每次给出棋盘上的一个子矩形,求这个子矩形中所有格子的 FF 之和。

输入格式

第一行三个正整数 T,n,mT,n,m。

接下来 TT 行,每行包含四个正整数 xl,xr,yl,yrx_l,x_r,y_l,y_r,表示该次询问的子矩形的 xx 坐标范围为 [xl,xr][x_l,x_r],yy 坐标范围为 yl,yry_l,y_r。

输出格式

对于每组数据,输出一行一个整数,表示答案对 109+710^9+7 取模的结果。

样例输入

3 10 10
3 4 5 6
5 5 7 8
3 10 3 10

样例输出

12
9
288

数据范围

对于所有数据,1≤T≤1051\le T\le 10^5,3≤n,m≤10183\le n,m\le 10^{18},3≤xl≤xr≤n3\le x_l\le x_r\le n,3≤yl≤yr≤m3\le y_l\le y_r\le m。

测试点编号 n,m≤n,m\le 特殊性质
1,21,2 50005000 无
3,43,4 10910^9 保证 xl=xr,yl=yrx_l=x_r,y_l=y_r
5,65,6 保证 2xl>yr,2yl>xr2x_l>y_r,2y_l>x_r
7,87,8 无
9,109,10 101810^{18}