古老的泰坦巨兽哥斯拉正在前往字节镇（Bytetown）的路上！

字节镇有 $n \times m$ 个街区，从上方俯瞰是一个 $n$ 行 $m$ 列的网格。网格的行和列分别从 $1$ 到 $n$ 和 $1$ 到 $m$ 编号。

哥斯拉会访问每个街区恰好一次。假设哥斯拉当前位于街区 $(i, j)$，他可以选择什么都不做，或者消耗 $e(i, j)$ 单位的能量以执行以下两种攻击方式之一。无论哪种方式，都会对字节镇造成 $d(i, j)$ 单位的伤害：

• 施放“水平原子吐息”，击中第 $i$ 行的所有街区。
• 施放“垂直原子吐息”，击中第 $j$ 列的所有街区。

注意，哥斯拉不会在同一个街区进行多次攻击。

哥斯拉既残忍又公平。因此，每个街区都将被“水平原子吐息”击中恰好一次，并且也将被“垂直原子吐息”击中恰好一次。请找出当哥斯拉消耗的总能量模 $4$ 的余数为 $k$ 时，他能造成的最大总伤害。你可以放心地假设哥斯拉总是有足够的能量。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n, m \le 75$)，表示行数和列数。

接下来的 $n$ 行，第 $i$ 行包含 $m$ 个整数 $d(i, 1), d(i, 2), \dots, d(i, m)$ ($1 \le d(i, j) \le 10^7$)。

接下来的 $n$ 行，第 $i$ 行包含 $m$ 个整数 $e(i, 1), e(i, 2), \dots, e(i, m)$ ($0 \le e(i, j) \le 3$)。

输出格式

输出四行。在第 $i$ 行 ($1 \le i \le 4$)，输出一个整数，表示当哥斯拉消耗的总能量模 $4$ 的余数为 $(i - 1)$ 时，能造成的最大总伤害。注意，如果无法达到该余数，请输出“-1”。

样例

样例输入 1

2 2
1 2
3 4
2 1
0 3

样例输出 1

-1
-1
10
-1

样例输入 2

3 3
1 2 3
4 5 6
7 8 9
2 1 0
0 3 2
1 2 1

样例输出 2

35
38
37
36