F. Fair Forgery
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The 2025 Pokemon Association Presidential Elections have just concluded! There were $$$N$$$ candidates running for the position of president, and $$$M$$$ votes were recieved. Each vote $$$i$$$ is a ranking of the $$$N$$$ candidates, which is a permutation $$$p_{i,1}, p_{i,2}, \dots, p_{i,N}$$$ of the integers from $$$1$$$ to $$$N$$$, with $$$p_{i, 1}$$$ ranked the highest, followed by $$$p_{i, 2}$$$, and so on, until the lowest ranked $$$p_{i, N}$$$.

Selina is in charge of tallying the votes. However, when she checked the list of voters, she realised that there were supposed to be $$$K$$$ voters, not $$$M$$$ voters! In other words, some voters may have submitted more than one vote, some may have not voted, or some non-voters may have somehow cast their vote. Selina does not want to redo the election due to suspicions in legitimacy of the votes, so she decided to forge $$$K$$$ votes to replace the $$$M$$$ votes recieved. However, the $$$K$$$ votes should not be too suspicious.

After some deliberation, she decided that if the $$$K$$$ votes satisfy the following condition, then they are probably not too suspicious:

For all integers $$$1 \leq t \leq K$$$, $$$1 \leq l \leq N$$$, if a candidate appears in the highest $$$l$$$ ranks in at least $$$\left \lceil \frac{t \cdot M}{K} \right \rceil$$$ of the $$$M$$$ received votes, then he/she should appear in the highest $$$l$$$ ranks in at least $$$t$$$ of the $$$K$$$ forged votes.

Selina proved non-constructively that she can always forge $$$K$$$ such votes regardless of the $$$M$$$ votes she recieves. However, she does not know how to actually forge these $$$K$$$ votes. Please help Selina with her forgery!

Input

The first line of the input contains 3 integers $$$N, M, K$$$ ($$$1 \leq M \leq 10^4$$$, $$$1 \leq N, K \leq 100$$$, $$$M \neq K$$$).

The next $$$M$$$ lines of the input each contain $$$N$$$ integers $$$p_{i, 1}, p_{i, 2}, \dots, p_{i, N}$$$, which is a permutation of $$$1$$$ to $$$N$$$.

Output

Output $$$K$$$ lines, where the $$$i^\text{th}$$$ line ($$$1 \leq i \leq K$$$) contains $$$N$$$ integers $$$q_{i, 1}, q_{i, 2}, \dots, q_{i, N}$$$ forming a permutation of $$$1$$$ to $$$N$$$, denoting the $$$i^\text{th}$$$ forged vote.

The $$$K$$$ votes should satisfy the condition mentioned.

Examples
Input
5 4 2
1 2 3 4 5
1 4 2 3 5
1 2 3 4 5
2 5 1 3 4
Output
1 2 3 4 5 
2 1 3 4 5
Input
10 2 4
1 4 5 2 7 6 10 9 3 8
5 6 1 8 7 3 4 9 10 2
Output
1 4 5 2 7 6 10 9 3 8 
1 4 5 2 7 6 10 9 3 8 
5 6 1 8 7 3 4 9 10 2 
5 6 1 8 7 3 4 9 10 2
Note

For the first sample, we can verify that the provided sample output satisfies the conditions. An example of an output that does not satisfy the conditions is:

1 2 4 5 3

1 2 5 3 4

This is because we may take $$$t = 1, l = 3$$$ in the condition: in the $$$l = 3$$$ highest ranks in the given $$$M$$$ votes, candidate 3 appears $$$2 \geq \left \lceil \frac{t \cdot M}{K} \right \rceil = \left \lceil \frac{1 \cdot 4}{2} \right \rceil = 2$$$ times, so it should appear at least $$$t = 1$$$ times in the 3 highest ranks in the output $$$K$$$ votes. However, it appears 0 times in the $$$3$$$ highest ranks in the output $$$K$$$ votes.