如果每个网格包含两个可能的括号之一——“(”或“)”,则二维数组称为括号数组。如果路径中的任何两个连续单元是侧面相邻的并且路径的每个单元位于前一个单元的下方或右侧,则通过二维数组单元的路径被称为单调路径。
如果从单元格 (1, 1) 到单元格 (n, m) 以某种单调方式写出括号而形成的任何字符串形成正确的括号序列,则大小等于 n × m 的二维数组称为正确的括号数组。
让我们定义比较两个相同大小的正确括号数组(a 和 b)的操作。让我们考虑一个给定的优先级二维数组 (c) — 一个大小相同的二维数组,包含从 1 到 nm 的不同整数。让我们在二维数组中找到这样的位置 (i, j),即 ai, j ≠ bi, j。如果有多个这样的位置,我们选择数字 ci, j 最小的一个。如果 ai, j = "(",则 a < b,否则 a > b。如果未找到位置 (i, j),则认为数组相等。
你的任务是找到第 k 个二维正确的括号数组。保证对于给定大小的n和m,将有不少于k个二维正确括号数组。
输入
第一行包含整数 n、m 和 k — 数组的大小和查找的正确括号数组的数量 (1 ≤ n, m ≤ 100, 1 ≤ k ≤ 1018)。然后给出一个优先级数组,n行每行包含m个数字,数字pi,j表示第i行中字符j的优先级(1≤pi,j≤nm,所有pi,j都不同)。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。
输出
打印第 k 个二维正确括号数组。
示例
输入 #1
1 2 1 1 2
输出 #1
()
输入 #2
2 3 1 1 2 3 4 5 6
输出 #2
(() ())
输入 #3
3 2 2 3 6 1 4 2 5
输出 #3
() )( ()
注意
在第一个样本中仅存在一个正确的二维括号数组。
在第二个和第三个示例中存在两个数组。
如果可以通过在序列中插入字符“+”和“1”来获得正确的算术表达式,则该序列称为正则括号序列。例如,序列《(())()》、《()》和《(()(()))》是规则的,而《)(》、《(()》和《(()))(》则不是。