The Ao–Tai Line is a high-altitude hiking route connecting Aoshan and Taibai Mountain in the Qinling Mountains. It is famous for its unpredictable weather, steep terrain, and thin oxygen, and is known as a dangerous route that "walks along the backbone of China." Along this route, each type of terrain corresponds to a different level of expedition difficulty and resource supply.
As an experienced explorer, Fanfan needs to plan a safe path from the starting point to the destination. Whenever Fanfan reaches a location, a certain amount of stamina is consumed, and some supplies are either consumed or replenished. We use an $$$n \times m$$$ mountain map to model this route, where each location is marked with a value.
You need to start from the upper-left corner $$$(1,1)$$$ and reach the lower-right corner $$$(n,m)$$$. You may move in the four directions: up, down, left, and right, and you may visit the same location multiple times.
Suppose the values of the locations along the explorer's path are $$$a_1, a_2, \ldots, a_k$$$, where $$$a_1$$$ is the value at the starting point $$$(1,1)$$$ and $$$a_k$$$ is the value at the ending point $$$(n,m)$$$. Define:
The stamina consumed as $$$OR = a_1 \mid a_2 \mid \ldots \mid a_k$$$ (bitwise OR),
The supplies remaining as $$$AND = a_1 \& a_2 \& \ldots \& a_k$$$ (bitwise AND).
Your task is to minimize the stamina consumed, and among all such paths, maximize the supplies remaining. Output the minimum stamina consumption and the maximum supplies remaining satisfying the condition.
The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 100$$$), denoting the number of test cases.
For each test case:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$ and $$$n \times m \leq 2 \cdot 10^5$$$), denoting the number of rows and columns of the matrix.
The next $$$n$$$ lines each contain $$$m$$$ non-negative integers $$$a_{ij} \lt 2^{30}$$$, representing the elements in the matrix.
It is guaranteed that for each test file, the sum of $$$n \times m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one line containing two integers, representing the minimum stamina consumption and the maximum supplies remaining that satisfy the conditions.
1 2 2 11 2 3 7
15 3
1 2 1 14 100
110 4
For the first sample:
The route $$$(1,1) \to (1,2) \to (2,2)$$$ has stamina consumption $$$15$$$ and supplies remaining $$$2$$$;
The route $$$(1,1) \to (2,1) \to (2,2)$$$ has stamina consumption $$$15$$$ and supplies remaining $$$3$$$;
There is no other route with smaller stamina consumption, so we choose the one with more supplies remaining. Therefore, the answer is $$$15\ 3$$$.
