Problem Description

Given an integer sequence $a_i$ of length $10^5$, you need to answer $t$ queries. Each query provides four values $l_1, l_2, r_1, r_2$, and you need to compute:

$$\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)$$

You do not have to process the queries online.

In this problem, the sequence $a_i$ is generated by the following code:

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;
}

Input Format

The first line contains an integer $t$, indicating the number of queries.

The next $t$ lines each contain four integers $l_1, r_1, l_2, r_2$.

Output Format

Output $t$ lines in total. Each line contains one number $\text{Sum}$, which is the answer.

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

9322587654
9025304064
1065645568
0

Hint

Constraints: $1\leq t\leq 40000$, $1\leq l_1 \leq r_1\leq 10^5$, $1\leq l_2 \leq r_2\leq 10^5$.

Translated by ChatGPT 5