题目描述

若二维数组在每个格子里写的都是两种括号之一——"(" 或 ")"——则称它为括号数组。穿过二维数组格子的一条路径称为单调路径，当且仅当路径中任何相邻两格都是四方向相邻、且路径中每个格子都位于前一个格子的下方或右方。

尺寸为 $n \times m$ 的二维数组称为合法括号数组，如果按某种单调路径从格子 (1,1) 走到 (n, m)、沿途把格子里的括号依次写出，得到的任何字符串都是合法括号序列。

定义两个同尺寸合法括号数组 $a$ 与 $b$ 的比较方式如下：给定一个优先级二维数组 $c$——同尺寸、含 1 到 $nm$ 之间互不相同的整数。找出二维数组中满足 $a_{i,j} \ne b_{i,j}$ 的位置 $(i, j)$；若这样的位置有多个，选 $c_{i,j}$ 最小的那个。若 $a_{i,j}$ = "("，则 $a \lt b$，否则 $a \gt b$。若找不到这样的位置，则两数组相等。

你的任务是求出第 $k$ 大的二维合法括号数组。保证对给定的 $n$ 与 $m$，合法括号数组至少有 $k$ 个。

输入格式

第一行包含整数 $n$、$m$ 和 $k$（$1 \le n, m \le 100$，$1 \le k \le 10^{18}$），表示数组尺寸与所求数组序号。接下来是优先级数组：$n$ 行、每行 $m$ 个数，$p_{i,j}$ 表示第 $i$ 行中第 $j$ 个字符的优先级（$1 \le p_{i,j} \le nm$，所有 $p_{i,j}$ 互不相同）。输入输出 64 位整数请不要用 %lld，建议用 cin、cout 流或 %I64d（本站评测环境下 %lld 同样可用）。

输出格式

输出第 $k$ 个二维合法括号数组。

1 2 1
1 2

()

2 3 1
1 2 3
4 5 6

()
(

3 2 2
3 6
1 4
2 5

()
)( ()

说明/提示

第一组样例中合法二维括号数组只有一个；第二、三组样例中各有两个。（其顺序由优先级数组决定。）