CF123C.Brackets

A two dimensional array is called a bracket array if each grid contains one of the two possible brackets — "(" or ")". A path through the two dimensional array cells is called monotonous if any two consecutive cells in the path are side-adjacent and each cell of the path is located below or to the right from the previous one.

A two dimensional array whose size equals n × m is called a correct bracket array, if any string formed by writing out the brackets on some monotonous way from cell (1, 1) to cell (n, m) forms a correct bracket sequence.

Let's define the operation of comparing two correct bracket arrays of equal size (a and b) like that. Let's consider a given two dimensional array of priorities (c) — a two dimensional array of same size, containing different integers from 1 to nm. Let's find such position (i, j) in the two dimensional array, that a__i, j ≠ b__i, j. If there are several such positions, let's choose the one where number c__i, j is minimum. If a__i, j = "(", then a < b, otherwise a > b. If the position (i, j) is not found, then the arrays are considered equal.

Your task is to find a k-th two dimensional correct bracket array. It is guaranteed that for the given sizes of n and m there will be no less than k two dimensional correct bracket arrays.

二维数组被称为括号数组，当且仅当其中每个格子包含两个可能的括号之一 — “(” 或 “)”。穿过二维数组格子的一条路径称为单调路径，当且仅当该路径中任意两个相邻格子是边相邻的（即共享一条边），且路径中每个格子均位于前一个格子的下方或右方。

一个大小为 $n \times m$ 的二维数组被称为正确的括号数组，当且仅当：对任意一条从格子 $(1, 1)$ 到格子 $(n, m)$ 的单调路径，将该路径上所有格子中的括号按经过顺序写出所构成的字符串，均为一个正确的括号序列。

下面我们定义两个大小相同（均为 $n \times m$）的正确括号数组 $a$ 和 $b$ 之间的比较操作。给定一个优先级二维数组 $c$ —— 它是一个与 $a$、$b$ 同尺寸的二维数组，其中包含 $1$ 到 $nm$ 的互不相同的整数。我们寻找满足 $a_{i,j} \ne b_{i,j}$ 的位置 $(i, j)$；若存在多个这样的位置，则选择其中 $c_{i,j}$ 值最小的那个。若在该位置上有 $a_{i,j} = \text{``(''}$，则定义 $a < b$；否则（即 $a_{i,j} = \text{``)''}$）定义 $a > b$。若不存在任何满足 $a_{i,j} \ne b_{i,j}$ 的位置，则认为这两个数组相等。

你的任务是找出第 $k$ 个二维正确括号数组。题目保证：对给定的 $n$ 和 $m$，存在的二维正确括号数组总数不少于 $k$ 个。

The first line contains integers n, m and k — the sizes of the array and the number of the sought correct bracket array (1 ≤ n, m ≤ 100, 1 ≤ k ≤ 1018). Then an array of priorities is given, n lines each containing m numbers, number p__i, j shows the priority of character j in line i (1 ≤ p__i, j ≤ nm, all p__i, j are different).

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

第一行包含整数 $n$、$m$ 和 $k$ —— 分别表示数组的大小以及所求的第 $k$ 个合法括号序列（$1 \leq n, m \leq 100$，$1 \leq k \leq 10^{18}$）。随后给出一个优先级数组，共 $n$ 行，每行包含 $m$ 个数字；其中 $p_{i,j}$ 表示第 $i$ 行中字符 $j$ 的优先级（$1 \leq p_{i,j} \leq nm$，所有 $p_{i,j}$ 互不相同）。

在 C++ 中，请勿使用 %lld 格式说明符读写 64 位整数。推荐使用 cin、cout 流，或 %I64d 格式说明符。

Print the k-th two dimensional correct bracket array.

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

In the first sample exists only one correct two-dimensional bracket array.

In the second and in the third samples two arrays exist.

A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters «+» and «1» into this sequence. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not.

第一个样例中仅存在一个正确的二维括号数组。

第二个和第三个样例中各存在两个数组。

若可以通过向该括号序列中插入字符「+」和「1」而得到合法的算术表达式，则称该括号序列为正则的（regular）。例如，序列「(())()」、「()」和「(()(()))」是正则的，而「)(」、「(()」和「(()))(」则不是。