Alien Dictionary#7049

Alien Dictionary

14 seconds

64 megabytes

Very easy

In the distant future, Earthlings have discovered a planet that was once home to intelligent beings unknown to humanity. Although the beings themselves are nowhere to be found, their library, filled with numerous written materials, has been uncovered. Scientists have eagerly begun deciphering these materials in hopes of discovering the whereabouts of these beings.

Upon analyzing the texts, it was determined that the alien writing system uses an alphabet consisting of $N$ letters, with each word comprising $M$ letters. Researchers have found what appears to be a dictionary, which is expected to greatly assist in understanding the language. The words in this dictionary are arranged not in lexicographical order, but in descending order of "importance." If two words share the same "importance," the lexicographically smaller word is listed first.

For any word $a_{1} a_{2} \dots a_{M}$ a_1a_2\dots a_M, its "importance" is calculated as the sum of the corresponding elements of the matrix:

W = p_{1, a_{1}} + p_{2, a_{2}} + \dots + p_{M, a_{M}}

W = p_{1,a_1} + p_{2,a_2} + \dots + p_{M,a_M}

Consider this example: with $N = 2$ N = 2 (number of letters) and $M = 3$ M = 3 (word length), there are $8$ possible words in this language. Let's list these words in lexicographical order. Here and throughout, the $k$ -th letter of the alien alphabet is represented by the $k$ -th letter of the Latin alphabet: aaa, aab, aba, abb, baa, bab, bba, and bbb. The matrix is as follows:

The importance of the words is calculated as:

aaa: 8 = 1 + 5 + 2;

aab: 12 = 1 + 5 + 6;

aba: 10 = 1 + 7 + 2;

abb: 14 = 1 + 7 + 6;

baa: 12 = 5 + 5 + 2;

bab: 16 = 5 + 5 + 6;

bba: 14 = 5 + 7 + 2;

bbb: 18 = 5 + 7 + 6,

and in the dictionary, the order of words is: bbb, bab, abb, bba, aab, baa, aba, aaa.

For further analysis, Earth scientists need to quickly determine which word appears at a specific position in this dictionary, following the described ordering rules: first by descending "importance," and if the "importance" is the same, in alphabetical order.

Given $N$ , $M$ , $K$ , and the matrix $p_{j, c}$ p_{j, c}, determine which word is at the $K$ -th position in the dictionary of alien beings.

Input

The first line contains three integers: $N$ , $M$ , and $K$ . Lines from $2$ to $(M + 1)$ (M+1) contain $N$ integers each — the corresponding elements of the matrix $p_{j, c}$ p_{j, c} ( $2 \leq N \leq 16$ 2 \leq N \leq 16, $1 \leq M \leq 10$ 1 \leq M \leq 10, $0 \leq p_{j, c} \leq 1 0^{8}$ 0 \leq p_{j, c} \leq 10^8, $1 \leq K \leq N^{M}$ 1 \leq K \leq N^M).

Output

The output should be a single line containing the word that is located at the $K$ -th position in the dictionary of alien beings.

Examples

Example 1