P2576 [ZJOI2005] Fantasy Origami

You are a girl who loves to daydream, especially about perfect ideals—“ideal circles,” “ideal equality,” “ideal materials,” “ideal optimal solutions”… Recently, by chance, you fell in love with origami. You tore pages from your notebook and folded all kinds of little tricks—little flowers, little grasses, little birds, little rabbits, little mice… page after page, until even the cover was folded into a paper crane. But you still didn’t feel satisfied. Finally… you couldn’t hold back your urge. You took a used scratch paper from your poor deskmate. Just as you were about to fold it the same way, you were amazed to find: this was not an ordinary scratch paper, but a very special one. It was so thin that its thickness could be ignored, so tough that it wouldn’t tear no matter how you pulled, and it could be folded in any way you wanted. You were thrilled—wasn’t this the “ideal material” you had dreamed of? As the saying goes, “after searching everywhere in iron shoes and finding nothing, it all comes without effort; seeking it a thousand times in dreams, suddenly turning back, there it is where the lights are dim!” You decided to fold something a bit more challenging to be worthy of such a good piece of paper.

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!”

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 $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.

- $1 \le t \le 10$. - $1 \le n, m \le 100$. Translated by ChatGPT 5