题目描述

A new puzzle which aims to conquer the game market is a fusion of Rubik's Cube and Fifteen. The board is an $H \times W$ frame with tiles with all numbers from $1$ to $H · W$ printed on them.

The only type of move that is allowed is flipping either one of the rows or one of the columns. Flipping reverses the order of the row's (or column's) elements. Below the third row is flipped:

You are given a board with tiles numbered in some arbitrary order. Determine a sequence of flips that brings the board to the nicely sorted position, if possible.

输入格式

The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

The description of each test case starts with an empty line. The next line contains two space-separated integers $W$ and $H (1 \leq W,H \leq 100) -$ the width and height of the puzzle, respectively. Each of the next $H$ lines contains $W$ space-separated integers $-$ the numbers printed on consecutive tiles.

输出格式

Print the answers to the test cases in the order in which they appear in the input. Start the output for each test case with the word POSSIBLE or IMPOSSIBLE, depending on whether it is possible to solve the puzzle. If a solution exists, print (in the same line) first the number of moves (possibly $0$) and then their descriptions, each consisting of a single letter $R$ or $C$ specifying whether we are to flip a row or a column, concatenated with the index of the row or column to flip.

Any solution will be accepted as long as it does not use more than $10 · W · H$ moves. Each test case is either solvable within this limit, or not solvable at all.

题目大意

有一个 $h\times w$ 的棋盘，每个位置上有一个在 $[1,h\times w]$ 的整数，且没有重复。每次操作可以翻转一行或一列（顺序上翻转）。

每个测试点共有 $T$ 组数据，每组数据都有 $h,w$ ，以及给定的 $h$ 行 $w$ 列的矩阵，要求对于每组数据，输出一行一个操作序列，使得操作后矩阵满足从上到下，从左到右递增。

如果无解，输出 IMPOSSIBLE。

如果有解，先输出 POSSIBLE，再输出操作序列的长度，然后输出操作序列。如果翻转第 $i$ 行，输出 Ri。如果翻转第 $i$ 列，输出 Ci，用空格隔开，中间不换行。

本题有 Special Judge, 操作序列长度不能超过 $10hw$。

$h,w \le 100$。

4

3 3
1 2 3
4 5 6
9 8 7

4 2
1 2 3 4
5 6 7 8

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

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

POSSIBLE 1 R3
POSSIBLE 0
POSSIBLE 3 R3 C3 R2
IMPOSSIBLE

提示

Time limit: 6 s, Memory limit: 128 MB.