C-穿越鳌太线_华中农业大学第十五届程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

鳌太线是一条连接秦岭鳌山与太白山的高海拔徒步路线，以其变幻莫测的气候、陡峭的地形和稀薄的氧气而闻名，被称为"行走在中华龙脊"上的艰险之路。在这条路线上，每一处地形都对应着不同的探险难度和资源补给情况。

钒钒作为一名经验丰富的探险者，需要规划一条从起点到终点的安全路径。每到达一个地点，钒钒会消耗一定体力并消耗/补充部分物资。我们用一个 $n \times m$ 的山区地图来模拟这条路线，每个地点都有一个数值标记。

你需要从左上角 $(1,1)$ 出发，到达右下角 $(n,m)$ 。你可以向上下左右四个方向移动，且可以重复经过同一个地点。

设探险者路径上的地点值依次为 $a_1, a_2, \ldots, a_k$ （其中 $a_1$ 是起点 $(1,1)$ 的值， $a_k$ 是终点 $(n,m)$ 的值），定义：

消耗的体力为 $OR = a_1 \mid a_2 \mid \ldots \mid a_k$ （按位或运算）

剩下的物资为 $AND = a_1 \& a_2 \& \ldots \& a_k$ （按位与运算）

要求在保证消耗的体力最小的情况下，最大化剩下的物资。请输出满足条件的最小体力消耗和最大物资剩余。

第一行包含一个整数 $T$ （ $1 \leq T \leq 100$ ），表示测试用例的数量。

对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ （ $1 \leq n, m \leq 10^5$ 并且 $n \times m \leq 2 \cdot 10^5$ ），表示矩阵的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个非负整数 $a_{ij} < 2^{30}$ ，表示矩阵中的元素。

保证对于一个测试点的所有数据， $n \times m$ 的和不超过 $2 \cdot 10^5$

对于每个测试用例，输出一行，包含两个整数，分别表示满足条件的最小体力消耗和最大物资剩余。

示例1

复制

复制

15 3

示例2

复制

复制

110 4

对于样例一，
(1,1) -> (1,2) -> (2,2) 的路线 消耗的体力为 15 ，剩余的物资为 2 ；
(1,1) -> (2,1) -> (2,2) 的路线 消耗的体力为 15 ，剩余的物资为 3 ；
除此并无消耗体力更少的方案，所以选择剩余物资更多的路线，故答案为 15 3。