Background

Translated from CEOI 2023 Day 1 T3 Balance.

Problem Description

Due to a hacker attack on the judging servers, the organizers decided to rejudge all submissions.

There are $N$ judging machines and $T$ problems (numbered $1, 2, \cdots, T$). The organizers have already decided which submissions each machine will judge (each machine has the same number of submissions, namely $S$ submissions; it is guaranteed that $S$ is an integer power of $2$). During the next $S$ minutes, in each minute, each judging machine will judge one submission.

Each submission belongs to some problem. Since the machine that stores the data is too fragile, it is required that, for every problem and for any two moments in time, the difference between the numbers of submissions judged for that problem at those two moments does not exceed $1$.

Please construct a schedule that satisfies the above condition.

Input Format

The first line contains $N, S, T$.

The next $N$ lines each contain $S$ integers, representing the problem IDs of the submissions assigned to this judging machine.

Output Format

Output $N$ lines, each with $S$ numbers, representing the problem IDs of the submissions that this judging machine should judge in order.

It can be proven that a solution always exists.

3 2 3
1 2
2 3
2 3

2 1
3 2
2 3

3 4 3
2 3 2 2
2 3 3 2
2 2 3 2

2 2 2 3
3 2 3 2
2 3 2 2

Hint

It is guaranteed that there exists a positive integer $k$ such that $S = 2 ^ k$. Also, $1 \le N, S, T \le 10 ^ 5$, and $NS \le 5 \times 10 ^ 5$.

• Subtask 1 ($10$ points): $S = 2$ and $N, T \le 20$.
• Subtask 2 ($15 + 5 + 5$ points): $S = 2$.
• Subtask 3 ($15 + 5 + 5$ points): $NS \le 10 ^ 4$.
• Subtask 4 ($20 + 10 + 10$ points): no other constraints.

For the last three subtasks, partial scores exist (corresponding to the points in parentheses):

• The first number is the score you can get if you can solve all testdata satisfying $T \le N$ and, for each problem, the number of submissions is divisible by $S$.
• The second number is the additional score you can get if you can solve all testdata satisfying $T \le N$.
• The third number is the additional score you can get if you solve the whole Subtask.

On Luogu, this problem is split into $10$ subtasks. For the original last three subtasks, in this problem they are each split into three subtasks in order (for example, the original Subtask 3 becomes subtasks $5, 6, 7$), and they have dependencies.

Translated by ChatGPT 5