题目描述

J 国发生了洪涝灾害，国王 JQH 正在规划救灾方案。

王国的土地可以被视为一个 $n\times m$ 的网格图，每个格子面积相同，格子 $(i,j)$ 的海拔近似为 $h_{i,j}$。由于 J 国地势较低，网格图外围的土地可视为拥有足够高的海拔；现在 J 国水位已经高出了国内地势最高的点，因此 JQH 考虑在某些位置放置强力海绵来吸水。

一个格子的强力海绵会吸走：

• 这个格子上原有的水；
• 以及所有能够流向这个格子的水（流动规则见后文“提示”）。

由于强力海绵生产缓慢，每 1 天只能生产 1 个海绵。海绵放置后不能移动。

你需要回答：对所有 $i\le K$，在第 $i$ 天（地图上一共放置了 $i$ 个海绵时），国内剩余水的体积之和的最小值是多少？
并且由于时间宝贵，你需要：

• 先最小化第 1 天剩余水量；
• 在此最优前提下再最小化第 2 天；
• 以此类推（字典序意义下的最小化）。

输入格式

• 第一行三个整数 $n,m,K$。
• 接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个数表示格子 $(i,j)$ 的海拔 $h_{i,j}$。

输出格式

设第 $i$ 天剩余水量为 $a_i$，你只需要输出一行一个整数：

其中 $\oplus$ 表示按位异或。

样例

样例 1

2 3 1
1 5 2
3 1 4

4

样例 2

2 3 2
1 5 2
3 1 4

6

样例 3

10 10 100
676275 872365 676275 600858 293517 423276 14682 358059 101917 17710
532804 257922 633281 611165 545041 611165 616352 867202 400683 577125
293517 160651 490142 202079 103823 515354 872365 350581 103823 381109
293517 647997 585576 867202 239821 892737 727503 700966 264055 773219
738088 294277 527649 5730 726537 101917 773219 293255 283032 544690
66082 178419 17710 892737 254909 700966 577762 738088 358059 872365
544690 95473 490142 401724 577125 293517 754155 738088 52130 700966
545041 178419 355976 203283 221364 998338 874838 101917 782901 532804
92623 216928 828426 892737 203283 578286 647997 782901 683370 616352
828426 647997 95473 691610 805671 577762 892737 294277 616352 293255

1118462

样例解释

**样例 1：**有 1 个海绵，可以放在 $(1,1)$ 或 $(2,2)$，答案都为 4。
例如放在 $(1,1)$，则格子 $(1,3)$、$(2,2)$ 上各剩余 2 体积水，总剩余为 4。

**样例 2：**第 1 天同样例 1。
第 2 天再放 1 个海绵在 $(1,1)$、$(2,2)$ 中尚未放置的那个格子上，可以发现剩余水量为 2。
注意：若第 1 天海绵放在 $(1,1)$，第 2 天不能把海绵放到 $(1,3)$、$(2,2)$ 等位置来“替换”，因为已放置海绵不能移动。
因此输出 $4\oplus 2=6$。

数据范围与提示

数据范围

对所有数据：

• $1\le n,m\le 500$
• $1\le K\le n\cdot m$
• $1\le h_{i,j}\le 10^6$

测试点分布（按题面整理）：

提示：水的流动（形式化）

• 称 $(x_0,y_0)$ 与 $(x_1,y_1)$ 相邻，当且仅当：

  $$|x_0-x_1|+|y_0-y_1|=1$$

• 如果存在一条路径 $(x_0,y_0),(x_1,y_1),\dots,(x_k,y_k)$ 和一个整数 $z$，满足：

  • 对所有 $0\le i<k$，$(x_i,y_i)$ 与 $(x_{i+1},y_{i+1})$ 相邻；
  • 格子 $(x_k,y_k)$ 上存在海绵；
  • 且$$z \le \max_{0\le i\le k} h_{x_i,y_i}$$

  则空间中 $(x_0,y_0,z)$ 的水会被吸收（因为它能沿路径流到海绵处）。

• 剩余水的体积之和：所有不会被吸收且满足 $z>h_{x,y}$ 的空间点 $(x,y,z)$ 的数量之和。