C. Скобочки
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Двумерный массив называется скобочным массивом, если в каждой клетки находится одна из двух возможных скобочек — «(» или «)». Путь по клеткам двумерного массива называется монотонным, если любые две последовательные клетки в пути имеют общую сторону, и при этом каждая клетка пути находится либо ниже, либо правее предыдущей.

Двумерный скобочный массив размером n × m называется правильным скобочным массивом, если любая строка, полученная выписыванием скобочек на каком-то монотонном пути из клетки (1, 1) в клетку (n, m), образует правильную скобочную последовательность.

Определим операцию сравнения двух правильных скобочных массивов (a и b) следующим образом. Пусть задан двумерный массив приоритетов (p) — двумерный массив, заполненный различными целыми числами от 1 до nm. Найдем такую позицию (i, j) в двумерном массиве, что ai, j ≠ bi, j. Если таких позиций несколько, выберем ту, где число pi, 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 показывает приоритет символа j в строке i (1 ≤ pi, j ≤ nm, все pi, j различные).

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных целых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Выходные данные

Выведите k-ый двумерный правильный скобочный массив.

Примеры
Входные данные
1 2 1
1 2
Выходные данные
()
Входные данные
2 3 1
1 2 3
4 5 6
Выходные данные
(()
())
Входные данные
3 2 2
3 6
1 4
2 5
Выходные данные
()
)(
()
Примечание

В первом примере существует лишь один правильный скобочный двумерный массив.

Во втором и третьем примерах существует по два варианта.

Напомним, что скобочная последовательность называется правильной, если путем вставки в нее символов «+» и «1» можно получить из нее корректное математическое выражение. Например, последовательности «(())()», «()» и «(()(()))» — правильные, в то время как «)(», «(()» и «(()))(» — нет.