题目描述

给定一个长度为 $10^5$ 的整数序列 $a_i$，现进行 $t$ 次询问，每次询问给出 $l_1,l_2,r_1,r_2$ 四个值，要求出：

$$\sum_{l \in [l_1,r_1]} \sum_{r \in [l_2,r_2]} (\max_{i \in [l,r]} a_i-\min_{i\in [l,r]} a_i) $$

的值。不要求强制在线。

本题中的序列 $a_i$ 由如下代码给定生成：

const int mod = 1e9;
long long fst = 1023, sec = 1025;
for (int i = 1; i <= 100000; i++) {
	a[i] = fst ^ sec;
	fst = fst * 1023 % mod;
	sec = sec * 1025 % mod;
}

输入格式

第一行一个数 $t$，表示询问组数。

接下来 $t$ 行，每行四个整数 $l_1, r_1, l_2, r_2$。

输出格式

一共 $t$ 行，每行一个数 $\text{Sum}$，表示答案。

输入输出样例 #1

输入 #1

4
1 3 5 7
2 4 6 8
1 1 9 9
9 9 1 1

输出 #1

9322587654
9025304064
1065645568
0

说明/提示

数据保证，$1\leq t\leq 40000$，$1\leq l_1<r_1\leq 10^5$，$1\leq l_2 \leq r_2\leq 10^5$。