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 ai, j ≠ bi, j. If there are several such positions, let's choose the one where number ci, j is minimum. If ai, 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.

Input

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 pi, j shows the priority of character j in line i (1 ≤ pi, j ≤ nm, all pi, 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.

Output

Print the k-th two dimensional correct bracket array.

Examples

Input

1 2 1
1 2


Output

()


Input

2 3 1
1 2 3
4 5 6


Output

(()
())


Input

3 2 2
3 6
1 4
2 5


Output

()
)(
()

Note

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.
import java.io.*;
import java.util.*;
import java.math.*;

public class P implements Runnable {

    public void run() {
        long startTime = System.nanoTime();

        int n = nextInt();
        int m = nextInt();
        long k = nextLong() - 1;
        int[][] p = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p[i][j] = nextInt() - 1;
            }
        }

        int[] cmp = new int[n + m - 1];
        for (int i = 0; i < cmp.length; i++) {
            int x = n * m;
            for (int t = 0; t < Math.min(i + 1, n); t++) {
                if (i - t < m) {
                    x = Math.min(x, p[t][i - t]);
                }
            }
            cmp[i] = x;
        }


        int[] a = new int[n + m - 1];
        boolean[] b = new boolean[n + m - 1];
        while (true) {
            int t = -1;
            for (int i = 0; i < a.length; i++) {
                if (!b[i] && (t == -1 || cmp[i] < cmp[t])) {
                    t = i;
                }
            }
            if (t == -1) {
                break;
            }
            b[t] = true;
            a[t] = 1;
            long x = count(a);
            if (k >= x) {
                k -= x;
                a[t] = 2;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                print(a[i + j] == 1 ? '(' : ')');
            }
            println("");
        }

        if (fileIOMode) {
            System.out.println((System.nanoTime() - startTime) / 1e9);
        }
        out.close();
    }

    long[][] f = new long[222][222];

    long go(int[] a, int i, int b) {
        if (b < 0) {
            return 0;
        }
        if (i == a.length) {
            return b == 0 ? 1 : 0;
        }
        if (f[i][b] != -1) {
            return f[i][b];
        }
        if (a[i] > 0) {
            f[i][b] = go(a, i + 1, a[i] == 1 ? b + 1 : b - 1);
            if (f[i][b] > 1.1e18) {
                f[i][b] = (long) 1.1e18;
            }
            return f[i][b];
        }
        f[i][b] = go(a, i + 1, b + 1) + go(a, i + 1, b - 1);
        if (f[i][b] > 1.1e18) {
            f[i][b] = (long) 1.1e18;
        }
        return f[i][b];
    }

    private long count(int[] a) {
        for (long[] t : f) {
            Arrays.fill(t, -1);
        }
        return go(a, 0, 0);
    }

    int get(int a, int b) {
        return b == 0 ? a : get(b, a % b);
    }

    //-----------------------------------------------------------------------------------

    private static boolean fileIOMode;
    private static String problemName = "a";
    private static BufferedReader in;
    private static PrintWriter out;
    private static StringTokenizer tokenizer;

    public static void main(String[] args) throws Exception {
        fileIOMode = args.length > 0 && args[0].equals("!");
        if (fileIOMode) {
            in = new BufferedReader(new FileReader(problemName + ".in"));
            out = new PrintWriter(problemName + ".out");
        } else {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }
        tokenizer = new StringTokenizer("");

        new Thread(new P()).start();
    }

    private static String nextLine() {
        try {
            return in.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    private static String nextToken() {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(nextLine());
        }
        return tokenizer.nextToken();
    }

    private static int nextInt() {
        return Integer.parseInt(nextToken());
    }

    private static long nextLong() {
        return Long.parseLong(nextToken());
    }

    private static double nextDouble() {
        return Double.parseDouble(nextToken());
    }

    private static BigInteger nextBigInteger() {
        return new BigInteger(nextToken());
    }

    private static void print(Object o) {
        if (fileIOMode) {
            System.out.print(o);
        }
        out.print(o);
    }

    private static void println(Object o) {
        if (fileIOMode) {
            System.out.println(o);
        }
        out.println(o);
    }

    private static void printf(String s, Object... o) {
        if (fileIOMode) {
            System.out.printf(s, o);
        }
        out.printf(s, o);
    }
}
