Bookshelf

Тавсифи масъала

Karimjon works at the National Library. In the section where Karimjon works, there is a large bookshelf of size $n \times m$, where rows are numbered from $0$ to $n-1$ and columns from $0$ to $m-1$.

The cell $(i, j)$ of the bookshelf contains a book with number $a[i][j]$. All book numbers on the shelf are distinct.

Karimjon can perform the following two operations:

• Row rearrangement: For every row, rearrange the books in that row in any order. The order can be chosen independently for each row.
• Column rearrangement: For every column, rearrange the books in that column in any order. The order can be chosen independently for each column.

Karimjon wants to sort the bookshelf. In a sorted bookshelf, row $0$ contains all books with numbers from $0$ to $m-1$ in increasing order, row $1$ contains all books with numbers from $m$ to $2m-1$ in increasing order, and so on. That is, for all and , the condition must hold.

Let $R$ be the minimum number of operations needed to sort the bookshelf. You are also given a number $T$, where $1 \leq T \leq 2$.

If $T = 1$, you only need to find the minimum number of operations $R$.

If $T = 2$, you need to find $R$ and also output the sequence of operations that achieves it.

Input Format

The first line contains three integers $n$, $m$, and $T$.

The next $n$ lines each contain $m$ integers --- the elements $a[i][0], a[i][1], \ldots, a[i][m-1]$.

Constraints:

• $1 \leq n, m \leq 100$
• $1 \leq T \leq 2$
• $0 \leq a[i][j] \leq n \cdot m - 1$

Output Format

If $T = 1$, print a single integer $R$ --- the minimum number of operations.

If $T = 2$, print the operations in order. For each operation, print a line containing either row or col, indicating whether it is a row rearrangement or a column rearrangement. Then print $n$ lines, each containing $m$ integers --- the state of the bookshelf after applying this operation. Finally, on the last line, print $R$ --- the total number of operations performed.

Each row rearrangement must only permute elements within each row (the multiset of elements in each row must remain the same compared to the state before this operation). Each column rearrangement must only permute elements within each column (the multiset of elements in each column must remain the same compared to the state before this operation).

After all operations, the bookshelf must be sorted, i.e. $a[i][j] = i \cdot m + j$ for all $i, j$.

The number of operations must equal $R$, the minimum possible.

Scoring

Notes

Example 1:

Here $T = 2$. The minimum number of operations is $R = 1$. We perform one row rearrangement: in row $0$, we rearrange $[1, 0]$ into $[0, 1]$; in row , we rearrange into .

Example 2:

Here $T = 1$, so we only need to output $R = 2$.

Example 3:

The minimum is $R = 3$. We perform: row rearrangement, then column rearrangement, then row rearrangement. After all three operations, the bookshelf is sorted.

2 2 2
1 0
3 2

row
0 1
2 3
1

2 3 1
0 4 2
5 1 3

2

5 3 2
10 9 11
14 5 12
1 4 7
3 8 13
2 6 0

row
11 9 10
12 14 5
4 7 1
8 3 13
0 2 6
col
0 2 1
4 3 5
8 7 6
11 9 10
12 14 13
row
0 1 2
3 4 5
6 7 8
9 10 11
12 13 14
3