#P2576. [ZJOI2005] 梦幻折纸

[ZJOI2005] 梦幻折纸

题目背景

你是一个喜欢幻想的小女孩,特别喜欢追求一些完美的理想的东西——“理想的圆”,“理想的均等”,“理想的材料”,“理想的最优解”……

最近,偶然的机会,你迷恋上了折纸。你把自己的作业本扯下来折成了各种各样的小把戏——小花,小草,小鸟,小兔子,小老鼠……一张又一张,直到作业本的封面都被你折成了纸鹤。但是你还是觉得不过瘾。

终于……你克制不住自己心中压抑的想法,从可怜的同桌那儿拿了一张用过的草稿纸。正当你打算用同样的方法折掉它的时候,你十分惊奇的发现:这不是一张普通的草稿纸,而是一张非常特殊的草稿纸:它薄得厚度可以忽略不计,柔韧得怎么撕也撕不破,而且无论怎么折都行。

你如获至宝,这不就是你梦寐以求的“理想的材料”吗?真所谓“踏破铁鞋无觅处,得来全不费功夫。梦里寻它千百度,蓦然回首,它却在灯火阑珊处 !”你决心要把它折成一个有难度一点的东西,才对得住一张这么好的纸。

题目描述

你仔细观察了一下纸的特点:

纸的大小为n(cm)×m(cm),上面等距离的印好了格线,n-1条横线和m-1条竖线(线的宽度忽略不计)。这些格线将纸分成了n×m个大小完全相同的正方形小格。你的同桌已经在每一块小格(i,j)上写下了一个互不相同的正整数P[i,j],1<=P[i,j]<=n×m。

“他干嘛在纸上写下这么些数字呢?”你看着这些数字,疑惑不解。

这时,你的同桌突然出现了,他发现你正拿着他的纸,看着上面的数字发呆。于是傻乎乎地对你说:

“我刚刚也想学你折纸,可是我很笨,只折出一个1(cm)×1(cm)的正方形,也就是一个n×m层纸的纸垛,每一层恰好是一个小格,所有的格线都恰好在正方形的边界上。”

“哦,折得不错,挺好的。”你口里说不错,心里却暗笑:没见过你这么笨的。居然把这么好的纸折成一个如此简单的正方形,简直是暴殄天物,罪过啊,罪过!

“是吗?你也觉得不错啊?我刚刚就在想,如果给这些小格编上号,最上面一层编为1,从上往下数的第i层编为i,那么能不能从这些编号复原出刚刚我折的那个图形呢?于是我就在这些格子上写下了它们的编号”

“这……”你一时语塞,确切的说,惊讶得说不出话来,原来一向傻乎乎的同桌脑子里也有这么深奥的想法。

“这样吧,如果你能根据我把我刚刚折的正方形折出来,那我就把这张纸送给你!” 同桌接着说,“不管你折法是否和我一样,只要折出来也是个1(cm)×1(cm)的正方形,从上往下数的第i层的编号恰好也是i,并且纸不能破,就算你折对了。”

“好啊,不过我先要检查检查你有没有骗我,要是你故意骗我或者自己粗心在编号的时候写错了数字而害得我折不出来,我可饶不了你!”

输入格式

第一行为整数t,代表输入数据的总数。

以下有t组数据,每组数据的结构如下:

第一行两个正整数n,m。

以下n行,每行m个正整数,相邻两个整数之间用一个空格隔开,描述矩阵p[i,j]。

输出格式

输出t行,对应t个输入数据。

对于第i组数据,输出AllRight——如果可以折出来;输出Cheat——如果折不出来。

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

提示

 t ≤ 10

 1 ≤ n,m ≤ 100