Summing (\max - \min) over Subarray Ranges

You are given a fixed integer sequence \(a_1, a_2, \dots, a_{10^5}\) 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;  // bitwise XOR
    fst = fst * 1023 % mod;
    sec = sec * 1025 % mod;
}

Then you are given \(t\) queries. Each query provides four integers \(l_1, l_2, r_1, r_2\). For every query, compute the value:

[ S = \sum_{l = l_1}^{r_1} \sum_{r = l_2}^{r_2} \Bigl(\max_{i \in [l, r]} a_i - \min_{i \in [l, r]} a_i\Bigr), ]

Note that for each pair \((l, r)\) you should only consider it if \(l \le r\) (otherwise the interval \([l, r]\) is undefined, and you may ignore that pair).

This problem does not require online query processing. Since the complete sequence is generated by the code above, you may precompute it. Beware that a brute force solution may be too slow if the query ranges are large, but the input guarantees that the ranges in the test cases are small.

inputFormat

The first line contains an integer \(t\) indicating the number of queries. Each of the next \(t\) lines contains four integers \(l_1, l_2, r_1, r_2\) separated by spaces.

Note: The array \(a\) is 1-indexed and has a fixed length of \(10^5\).

outputFormat

For each query, output one line containing a single integer, the value of \(S\) defined as above.

sample

1
1 1 1 1

0