筱玛的网格
题号：NC21819
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

筱玛是一个快乐的男孩子。
最近筱玛喜欢网格图，所以他想出了一个好玩的题。
网格图的每一个格子上都有字符 '(' 或 ')'。定义一个 n × m 的网格图是快乐的，当且仅当这个网格图满足任意一条从 (1, 1) 出发到 (n, m) 的最短路径都构成一个合法的括号序列。
筱玛对每一个格子 (i, j) 都有一个互不相同的喜爱程度 val[i][j]。
对于任意一个快乐网格图，按照喜爱程度从小到大将格中字符依次写下，可以得到一个字符串。
他希望得到一个网格图，使得其对应的字符串在所有 n × m 的快乐网格图对应的字符串中字典序第 k 小。
其中 '(' 的字典序小于 ')'。
下面我们给出括号序列的定义：
  1. 空序列是合法的括号序列；
  2. 如果 S 是合法括号的序列，那么 (S) 也是合法的括号序列；
  3. 如果 A 和 B 都是合法的括号序列，那么 AB 也是合法的括号序列。

输入描述:

输入共 n + 1 行。
第一行三个整数分别表示 n, m, k。
接下来 n 行，每行 m 个整数，表示 val[i][j]。
保证 n + m - 1 是偶数。
保证快乐网格图总数 ≥ k。

输出描述:

输出共 n 行，每行一个字符串，长度为 m。
表示对应字符串字典序第 k 小的网格图。
示例1

输入

复制 
4 3 4
4 3 8
2 12 11
1 5 7
6 10 9

输出

复制 
(()
()(
)()
())

备注:

n ≤ 200; m ≤ 200; k ≤ 109
val[i][j]是一个的排列。
输入都是正整数。