**Note: Chapters [1](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D1) and [2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D2) are strictly less difficult versions of this problem, with differences in bold. Solutions to later chapters can be directly applied to solve earlier ones.**

Facebulk Inc. is a mining company who just released its latest performance reports. Backed by strong earnings, the company is now seeking to grow its infrastructure by surveying ore samples across \(T\) new sites using its patented robotics tech.

A given site has been excavated after much drilling and blasting, forming a rectangular pit that's \(R\) rows long (numbered from \(1\) to \(R\)) by \(C\) columns wide (numbered from \(1\) to \(C\)) by \(10^9\) cm deep. The pit consists of a grid of \(R*C\) platforms, where the platform at row \(i\) and column \(j\) (denoted as platform \((i, j)\)) is at height \(H_{i,j}\) cm from the bottom of the pit.

Unfortunately, there's a forecast of heavy rain — rainwater is about to start slowly flooding the pit. The water level is initially at height \(0\), and will eventually fill up the entire pit at height \(10^9\) cm.

Your supervisor wants \(R*C\) ore samples to be collected and analyzed, one from each platform, based on the following humidity requirements: the sample from platform \((i, j)\) is *only* worthwhile if collected at some point while the water level is strictly between \(S_{i,j}\) and \(S_{i,j}+1\) cm.

In an attempt to accomplish this, you'll dispatch \(0\) or more remote-control robots before it starts to rain, each at an initial platform of your choice. Multiple robots may occupy the same platform. At any point in time, you can command any robot at some platform \((i, j)\) to move to an adjacent platform (any platform \((i', j')\) such that \(|i-i'| + |j-j'| = 1\)), or to collect an ore sample from its current platform. Rainwater will flood slowly enough that the robots have time to execute an arbitrary number of commands before water increases from any height of \(x\) to \(x+1\) cm.

If a robot is ever on platform \((i, j)\) while the water level is greater than or equal to \(H_{i,j}\) (either because the robot moved to that platform or because the water level increased while the robot was present on it), the robot will short circuit and stop executing any more commands.

**To make matters more complicated, before you get to start implementing any plan, your supervisor will keep changing their mind about what samples are worthwhile.** They'll change their mind \(K\) times, such that the \(i\)th time, they'll decide that \(S_{A_i,B_i}\) will henceforth actually be equal to \(U_i\) (until they potentially change their mind about it again).

Considering the situation after your supervisor has changed their mind the first \(i\) times, let \(X_i\) be the maximum number of desired ore samples which could theoretically be collected, and let \(Y_i\) be the minimum number of robots which must theoretically be dispatched to collect that many samples. Please compute the sum of \(X_{1..K}\) and the sum of \(Y_{1..K}\).

**Your supervisor insists that you finish assessing the \(i\)th situation and computing \(X_i\) and \(Y_i\) before they tell you how they've changed their mind for the \((i+1)\)th time.** To that end, you will not be given \(A_{1..K}\), \(B_{1..K}\), and \(U_{1..K}\) directly; you'll instead be given different sequences of values \(A'_{1..K}\), \(B'_{1..K}\), and \(U'_{1..K}\).

Given \(A_1 = A'_1\), \(B_1 = B'_1\), and \(U_1 = U'_1\), for each \(i \ge 2\) you must compute \(A_i = A'_i \oplus Y_{i-1}\), \(B_i = B'_i \oplus Y_{i-1}\), and \(U_i = U'_i \oplus Y_{i-1}\) for yourself (where \(\oplus\) is the bitwise xor operator, `'^'` in many programming languages).

# Constraints

\(1 \le T \le 45\)
\(1 \le R, C \le 1{,}000{,}000\)
\(R*C \le 1{,}000{,}000\)
\(1 \le H_{i,j} \le 1{,}000{,}000{,}000\)
\(0 \le S_{i,j} < 1{,}000{,}000{,}000\)
\(1 \le K \le 1{,}000{,}000\)
\(1 \le A_i \le R\)
\(1 \le B_i \le C\)
\(0 \le U_i < 1{,}000{,}000{,}000\)
\(0 \le A'_i, B'_i, U'_i \le 2{,}000{,}000{,}000\)

The sum of \(R*C + K\) across all sites is at most \(5{,}000{,}000\).

# Input

Input begins with an integer \(T\), the number of sites to be surveyed. For each site, there is first a line containing \(2\) space-separated integers, \(R\) and \(C\). Then, \(R\) lines follow, the \(i\)th of which consists of \(C\) space-separated integers, \(H_{i,1..C}\). Then, another \(R\) lines follow, the \(i\)th of which consists of \(C\) space-separated integers \(S_{i,1..C}\). Then, a line will follow containing the single integer \(K\). Then, \(K\) lines will follow, the \(i\)th of which contains \(3\) space-separated integers, \(A'_i\), \(B'_i\), and \(U'_i\).

# Output

For the \(i\)th site, print a line containing *"Case #i: "* followed by \(2\) space-separated integers, the sum of \(X_{1..K}\), and the sum of \(Y_{1..K}\).

# Sample Explanation

At the first site, \(S_{1,1}\) will immediately get changed to \(98\). If you were to then dispatch a single robot at platform \((1, 2)\), it could wait there until the water level exceeds \(98\) cm, collect an ore sample from platform \((1, 2)\), move to platform \((1, 3)\), wait until the water level exceeds \(99\) cm, and finally collect an ore sample from platform \((1, 3)\). No matter how many robots were to be dispatched, they could not collect an ore sample from platform \((1, 1)\) after the water level exceeds \(98\) cm (as the platform would already be flooded), meaning that \(1\) robot collecting \(2\) samples is the best that can be done. Therefore, \(X = [2]\) and \(Y = [1]\).

At the second site, once \(S_{1,1}\) gets changed to \(5\), the ore sample at platform \((1, 1)\) would be possible to collect (by a single robot). Therefore \(X_1 = Y_1 = 1\). In turn, \(A_2 = 0 \oplus 1 = 1\), \(B_2 = 0 \oplus 1 = 1\), and \(U_2 = 14 \oplus 1 = 15\). Once \(S_{1,1}\) gets changed to \(15\), the ore sample would no longer be possible to collect. Therefore, \(X_2 = Y_2 = 0\), and so \(A_3 = 1 \oplus 0 = 1\), \(B_3 = 1 \oplus 0 = 1\), and \(U_3 = 5 \oplus 0 = 5\). Once it gets changed back to \(5\), the sample would once again be possible to collect. Therefore, \(X_3 = Y_3 = 1\), and the sums of \(X_{1..K}\) and of \(Y_{1..K}\) are both equal to \(2\).

At the third site, a single robot dispatched anywhere would be able to move around and collect samples from all 6 platforms before the water level reaches \(1\) cm — therefore, \(X = [6]\) and \(Y = [1]\).

At the fourth site, no samples can be collected before all \(6\) platforms get flooded — therefore, \(X = [0]\) and \(Y = [0]\).

At the fifth site, once \(S_{1,2}\) gets changed to \(2\), samples at platforms \((1, 1)\) and \((1, 3)\) would be possible to be collect, though not by a single robot — therefore, \(X_1 = 2\) and \(Y_1 = 2\). Overall, \(X = [2, 2, 3, 3, 4]\) and \(Y = [2, 1, 1, 1, 2]\), with \(A = [1, 1, 2, 1, 2]\), \(B = [2, 1, 2, 3, 1]\), and \(U = [2, 1, 1, 2, 2]\).

At the sixth site:
- \(X = [68, 67, 66, 67, 67, 66, 65, 65, 64, 65]\)
- \(Y = [12, 12, 12, 12, 12, 11, 11, 11, 10, 10]\)
- \(A = [3, 1, 2, 3, 4, 4, 4, 3, 4, 3]\)
- \(B = [17, 18, 10, 4, 4, 20, 7, 13, 8, 18]\)
- \(U = [17, 69, 64, 12, 17, 100, 84, 20, 42, 53]\)

*Note: These sample cases represent the same data as those in [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D2), just in a different format.*