Description

You carefully observe the features of the paper:

The paper has size $n \times m$, with equally spaced grid lines printed on it: $n - 1$ horizontal lines and $m - 1$ vertical lines (line width ignored). These grid lines divide the paper into $n \times m$ small squares of exactly the same size. Your deskmate has already written on each small square $(i, j)$ a distinct positive integer $P_{i, j}$ with $1 \le P_{i, j} \le n \times m$.

“Why did he write so many numbers on the paper?” You look at these numbers, puzzled.

At this moment, your deskmate suddenly shows up. He finds you holding his paper, staring at the numbers in a daze. So he says, a bit silly:

“I just tried to learn origami from you, but I’m clumsy. I only folded a $1 \times 1$ square, that is, a stack of $n \times m$ layers of paper, with each layer exactly one small square, and all grid lines exactly on the boundary of the square.”

“Oh, that’s nice, pretty good.” You say it’s good, but secretly laugh: never seen anyone as clumsy as you. Folding such a great paper into such a simple square—what a waste!

“Really? You also think it’s good? I was just thinking, if we number these small squares, label the top layer as $1$, and label the $i$-th layer counted from top to bottom as $i$, can we reconstruct the exact figure I folded from these numbers? So I wrote their labels on the squares.”

“This…” You are at a loss for words—more precisely, so surprised you cannot speak. Turns out your usually silly deskmate has such a deep thought.

“How about this: if you can fold the square I folded just now based on my labels, I’ll give you this paper!” he continues. “No matter whether your sequence of folds is the same as mine or not, as long as you also get a $1 \times 1$ square, the $i$-th layer from top to bottom is exactly labeled $i$, and the paper is not torn, then you did it right.”

“Alright, but I’ll first check whether you’re trying to fool me. If you deliberately cheat or made careless mistakes when writing the labels so that I cannot fold it, I won’t let you off!”

Input Format

The first line contains an integer $t$, the total number of testcases.

Then there are $t$ testcases, each with the following structure:

• The first line contains two positive integers $n, m$.
• The next $n$ lines each contain $m$ positive integers, separated by a single space, describing the matrix $P_{i, j}$.

Output Format

Output $t$ lines, one for each testcase.

For the $i$-th testcase, output AllRight if it can be folded as required; otherwise output Cheat if it cannot.

4

1 7
3 1 7 6 5 4 2

2 2
1 2
3 4

2 3
2 1 6
3 4 5

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

AllRight
Cheat
AllRight
AllRight

Hint

• $1 \le t \le 10$.
• $1 \le n, m \le 100$.

Translated by ChatGPT 5