402381: GYM100741 C Reordering Ones

Given a board of size N * M. The rows are numbered from 1 to N, and the columns are numbered from 1 to M. Each cell of the board contains either 0 or 1.

You can apply 2 types of operations:

1. swapCol(i, j), meaning you can swap 2 different columns
2. swapRow(i, j), meaning you can swap 2 different rows.

You have a function valid(x1, y1, x2, y2), which returns true if and only if every cell in the sub-board with 2 opposite corners (x₁, y₁), (x₂, y₂) contains all 1.

You need to find maximum value of (x₀ + y₀), such that it is possible to apply the operations, so that valid(1, 1, x0, y0) = true. However, everybody is only interested in solutions where x₀ + y₀ > max(m, n).

On the first line of input there are two integers N and M (1 ≤ N, M ≤ 1000) – the size of the matrix. On the following N lines there are M integers each – the elements of the matrix, either 0 or 1.

On the first line of output print the values x₀ and y₀ giving the maximal possible sum (x₀ + y₀).

On the next line of output print the number R – the number of operations.

On the following R lines output the operations itself in such format T i j, where T is the what is swapped ('C' for columns and 'R' for rows), i and j are the indexes of rows/columns being swapped.

If there are multiple solutions, output any of them.

If there is no solution such that x₀ + y₀ > max(m, n), print single line with "0 0".

3 3
0 1 1
1 1 0
1 1 1

1 3
1
R 1 3

3 1
0
1
1

0 0