Problem D
Chuck
You are given an matrix of $R$ rows and $C$ columns. All elements of the matrix have absolute value smaller than or equal to $10^4$. You may perform the following operations:
|
Operation |
Notation |
Example |
|
|
Rotate $i$-th row of the matrix $k$ elements right ($1 \leq i \leq R$, $1 \leq k < C$). |
$\mathrm{rotR}\ i\ k$ |
$\mathrm{rotR}\ 3\ 1$ |
$ \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix} \mapsto \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 9 & 7 & 8 \\ 10 & 11 & 12 \end{pmatrix} $ |
|
Rotate $j$-th column of the matrix $k$ elements down ($1 \leq j \leq C$, $1 \leq k < R$). |
$\mathrm{rotS}\ j\ k$ |
$\mathrm{rotS}\ 3\ 1$ |
$ \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix} \mapsto \begin{pmatrix} 1 & 2 & 12 \\ 4 & 5 & 3 \\ 7 & 8 & 6 \\ 10 & 11 & 9 \end{pmatrix} $ |
|
Multiply all elements in the $i$-th row by $-1$, if and only if none of them were multiplied before ($1 \leq i \leq R$). |
$\mathrm{negR}\ i$ |
$\mathrm{negR}\ 2$ |
$ \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix} \mapsto \begin{pmatrix} 1 & 2 & 3 \\ -4 & -5 & -6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix} $ |
|
Multiply all elements in the $j$-th column by $-1$, if and only if none of them were multiplied before ($1 \leq j \leq C$). |
$\mathrm{negS}\ j$ |
$\mathrm{negS}\ 1$ |
$ \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix} \mapsto \begin{pmatrix} -1 & 2 & 3 \\ -4 & 5 & 6 \\ -7 & 8 & 9 \\ -10 & 11 & 12 \end{pmatrix} $ |
Using a limited number of these operations, you need to maximize the sum of all the elements of the matrix.
Input
The first line of input contains two integers $R$ and $C$ ($1 \leq R, C \leq 100$), the number of rows and columns. The next $R$ lines contain $C$ integers each. All integers are by their absolute value smaller than $10^4$.
Output
The first line of output should contain two integers, the maximal sum obtainable and the number of operations used. We shall call this number $T$, and it must hold that $T \leq 5RC$. The next $T$ lines should contain any sequence of operations leading to the sum. Each operation should follow the notation defined in Table 1. For details look at sample test cases.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 1 -2 5 200 -8 0 -4 -10 11 4 0 100 |
345 2 rotS 2 1 negR 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 8 -2 7 1 0 -3 -4 -8 3 |
34 4 rotR 1 1 rotS 3 1 negR 2 negR 3 |