题目描述

译自 COCI 2010.03.06 T6. CHUCK

给你一个 $R$ 行 $C$ 列的矩阵 $A$，$|A_{i,j}|\leq 10^4$。请使用若干次下述操作（次数尽量少），使得矩阵中 $\sum_i \sum_j A_{i,j}$ 尽可能大。

操作类型及示例：

1. $\texttt{rotR i k}$：将第 $i$ 行的元素循环右移 $k$ 位

   $$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ rotR 3 1 }}\begin{pmatrix}1&2&3\\4&5&6\\9&7&8\\10&11&12\end{pmatrix} $$

2. $\texttt{rotS j k}$：将第 $j$ 列的元素循环下移 $k$ 位

   $$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ rotS 3 2 }}\begin{pmatrix}1&2&9\\4&5&12\\7&8&3\\10&11&6\end{pmatrix} $$

3. $\texttt{negR i}$：将第 $i$ 行的元素全部乘以 $-1$

   • 该操作当且仅当该行任何一个元素均未乘以 $-1$ 时有效
   $$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ negR 2 }}\begin{pmatrix}1&2&3\\-4&-5&-6\\7&8&9\\10&11&12\end{pmatrix} $$

4. $\texttt{negS j}$：将第 $j$ 列的元素全部乘以 $-1$

   • 该操作当且仅当该列任何一个元素均未乘以 $-1$ 时有效
   $$\begin{pmatrix}1&2&3\\0&0&0\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ negS 1 }}\begin{pmatrix}-1&2&3\\0&0&0\\-7&8&9\\-10&11&12\end{pmatrix} $$

输入格式

第一行：$R,C$。 接下来 $R$ 行：矩阵 $A$。

输出格式

第一行包含两个整数，第一个整数为 $\sum_i \sum_j A_{i,j}$ 的最大值，第二个数为操作数量 $T$。 接下来 $T$ 行，每行包含一组操作。

样例 1

输入：

3 4
1 -2 5 200
-8 0 -4 -10
11 4 0 100

输出：

345 2
rotS 2 1
negR 2

样例 2

输入：

3 3
8 -2 7
1 0 -3
-4 -8 3

输出：

34 4
rotR 1 1
rotS 3 1
negR 2
negR 3

数据范围与提示

$1≤R,C≤100$, $|A_{i,j}|≤10^4$。

评分标准：

• 若你求了个错误的最大和，或是执行的操作中有无效的，该测试点不得分；
• 若 $T≤ 5\cdot RC$，你将得到该点的所有分数；
• 若 $5\cdot RC<T≤10^5$，你将得到该点 $50\%$ 的分数；
• 若 $T>10^5$，你将得不到该点的任何分数。