**Note: Chapters [2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D2) and [3](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D3) are strictly more difficult versions of this problem, with differences highlighted 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.

Let \(X\) be the maximum number of desired ore samples which can be collected, and let \(Y\) be the minimum number of robots which must be dispatched to collect that many samples. Please compute \(X\) and \(Y\).

# Constraints

\(1 \le T \le 55\)
\(1 \le R, C \le 1{,}000{,}000\)
\(R*C \le 1{,}000{,}000\)
\(1 \le H_{i,j} \le 10^9\)
\(0 \le S_{i,j} < 10^9\)

The sum of \(R*C\) 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}\).

# Output

For the \(i\)th site, print a line containing *"Case #i: "* followed by \(2\) space-separated integers, the maximum number of desired ore samples which can be collected, and the minimum number of robots which must be dispatched to collect that many samples.

# Sample Explanation

At the first site, if you dispatch a single robot at platform \((1, 2)\), it can 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 are dispatched, they cannot 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.

At the second site, a single robot dispatched anywhere can move around and collect samples from all \(6\) platforms before the water level reaches \(1\) cm.

At the third site, no samples can be collected before all \(6\) platforms get flooded.

At the fourth site, samples at platforms \((1, 1)\) and \((1, 3)\), but not by a single robot.