Brackets

题意翻译

括号数组是一个只有 “(” 或 “)” 两类字符的二维数组。括号数组中的合法路径只能从任意位置开始，向右或向下移动。如果一个 n×m 括号数组中从 (1,1) 到 (n,m) 的所有路径经过的字符构成的字符串均为可以完全匹配的括号序列，则这个括号数组可以被称作神奇数组。 现在定义一种比较神奇数组大小的方式，假设这两个数组分别为 a 和 b ，两个数组行列均相等，找到数组中满足条件 a i,j=b i,j 的位置 (i,j) ，如果有多个这样的位置，则选择优先级编号最小的位置（数据中已给出），如果此时 a i,j= “(” ，则 a<b ，否则 a>b ，如果不存在这样的位置，则 a 和 b 相等。 根据以上定义，请找出第 k 大的神奇数组，数据保证有解。 输入描述 第一行输入三个整数 n , m , k ，分别表示数组大小和要寻找的数组编号 以下 n 行 m 列给出优先级编号 p i,j保证p i,j均不相等)。 输出描述 输出第 k 大的神奇数组

题目描述

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&lt;b $ , otherwise $ a&gt;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.

输入输出格式

输入格式

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<=10^{18} $ ). 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.

输出格式

Print the $ k $ -th two dimensional correct bracket array.

输入输出样例

输入样例 #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

()
)(
()

说明

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.