Problem J. Rectangle Radar Scanner

There are $n$ houses on the ground, labeled by $1$ to $n$. The $i$-th house is located at $(i,y_i)$, and there is a spy transmitter with energy $w_i$ inside the $i$-th house.
Little Q has a rectangle radar scanner, which can find all the transmitters within the range $[xl,xr]\times[yl,yr]$. That means a transmitter located at $(x,y)$ can be found if $xl\leq x\leq xr$ and $yl\leq y\leq yr$.
Your task is to achieve the scanner efficiently.
Given $m$ queries $xl_i,xr_i,yl_i,yr_i$, for each query, please find all the transmitters within the range, then report the product of their energy and the maximum/minimum energy among them.
To reduce the large input, we will use the following generator. The numbers $a_0,b_0,c_0,d_0,p,q,r$ and $MOD$ are given initially. The values $a_i,b_i,c_i,d_i,xl_i,xr_i,yl_i,yr_i$ are then produced as follows :
\begin{eqnarray*}
a_i&=&(p\times a_{i-1}+q\times b_{i-1}+r)\bmod MOD\\
b_i&=&(p\times b_{i-1}+q\times a_{i-1}+r)\bmod MOD\\
c_i&=&(p\times c_{i-1}+q\times d_{i-1}+r)\bmod MOD\\
d_i&=&(p\times d_{i-1}+q\times c_{i-1}+r)\bmod MOD\\
xl_i&=&\min(a_i\bmod n,b_i\bmod n)+1\\
xr_i&=&\max(a_i\bmod n,b_i\bmod n)+1\\
yl_i&=&\min(c_i\bmod n,d_i\bmod n)+1\\
yr_i&=&\max(c_i\bmod n,d_i\bmod n)+1
\end{eqnarray*}

The first line of the input contains an integer $T(1\leq T\leq3)$, denoting the number of test cases.
In each test case, there is an integer $n(1\leq n\leq 100000)$ in the first line, denoting the number of houses.
In the next $n$ lines, each line contains $2$ integers $y_i,w_i(1\leq y_i\leq n,1\leq w_i\leq 10^9)$, describing a house.
Then in the next line, there are $10$ integers $m,a_0,b_0,c_0,d_0,p,q,r,MOD,k$, describing the queries. It is guaranteed that $1\leq m\leq 10^6$ and $5\leq a_0,b_0,c_0,d_0,p,q,r,MOD,k\leq 10^9$.

Since the output file may be very large, let's denote $prod_i$ as the product of of the $i$-th query, $max_i$ as the maximum energy of the $i$-th query, and denote $min_i$ as the minimum energy of the $i$-th query. Note that when there are no avaliable transmitters, then $prod_i=max_i=min_i=0$.
For each test case, you need to print a single line containing an integer $answer$, where :
\begin{eqnarray*}
answer&=&\sum_{i=1}^{m} ((prod_i\bmod k)\oplus max_i\oplus min_i)
\end{eqnarray*}
Note that ``$\oplus$'' denotes binary XOR operation.

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

68

2018 Multi-University Training Contest 3