【agc006_e】Rotate 3x3

首先我们推规律。发现无论怎么旋转都是旋转点左、右侧的两列交换后上下翻转，旋转点所在的列只有上下翻转。所以翻转前若xyz三个数在同一列，无论怎么翻转，翻转后xyz还在同一列上。
于是我们设初始网格的第一列为a，若这一列被翻转，则为大写字母A。
同理，那么初始网格就是
a b c d e f . . . abcdef... abcdef...
于是对于原来的序列 a b c abc abc对于B为中心旋转操作后为 B A C BAC BAC

那么对于n=5，我们需要什么操作呢？
显然至少有两个，第一个用来交换列之间的顺序，另一个用来改变列的大小写。
a b c d e a D C B e c d A B e c d E b a e D C b a e B c d a C b E d a C b A D e a B c D e   . . . ① abcde\\ aDCBe\\ cdABe\\ cdEba\\ eDCba\\ eBcda\\ CbEda\\ CbADe\\ aBcDe\ ...① abcdeaDCBecdABecdEbaeDCbaeBcdaCbEdaCbADeaBcDe ...①
看到了吧，第一个操作，允许把 a b c d e abcde abcde变为 a B c D e aBcDe aBcDe。
这样我们可以改变列的大小写。显然只能在相邻的同奇偶列中同时改变大小写。
对于①式，我们继续推下去。
a B c D e a d C b e   . . . ② aBcDe\\ adCbe\ ...② aBcDeadCbe ...②
第二个操作结合第一个操作，我们就可以把 a b c d e abcde abcde变为 a d C b e adCbe adCbe。
这样我们可以改变列的顺序。注意到所有交换顺序都只能在同奇偶的列中交换。
观察一下，如果我们想要改变两个同奇数列或同偶数列的大小写，什么都不会影响。注意我这里说的两个不是必须是相隔一列的两列，因为大小写是可以转走的，为什么？
对于② a d C b e adCbe adCbe
将①对于b代入得到
a d c b E adcbE adcbE
我们就轻松的把大小写转走了。当然我们可以把大写或小写转到任意一个与这一行奇偶性相同的列。
现在我们分开奇偶列考虑。对于原符号列中的奇数列，考虑计算数列中的逆序对，我们至少要相互交换这么多次才能把他弄回最终奇数列的顺序，这绝对是不可避免的。观察②式，我们每交换一次奇数列中的数，都会让偶数列中的一个数大小写改变（改变可以在偶序列中传递）。
交换回最终奇数列顺序来之后，我们就可以改变大小写了，只要奇数列的大写数量是偶数，我们必可以全部把他变成小写。不会影响偶数列。
我们考虑对于一开始的奇数列，设他的大写字母数为K，那么最终我们肯定要消灭完这些大写字母。显然奇数列交换顺序不会影响奇数列中大写字母的个数。所以在偶数列不影响奇数列的前提下，只要K是偶数，我们就一定可以消掉原来的大写字母，让奇数列最终满足条件。
所以偶数列什么时候会影响奇数列呢？根据②式可得，只有交换时。对于每一次交换，都会让奇数列的任意一个数改变大小写（同理因为奇数列之中可以传递大小写变化）。偶数列交换的次数也决定着奇数列变换大小写的次数。
如果我们①操作是一次改变一个，那么就很皆大欢喜，我搞好后你偶数列不管怎么改，你改哪个我就抵消哪个，不会影响。这题①操作是一次改变两个，也就是说①号操作帮你在不改变大写字母数量奇偶性的前提下，大写字母数量可以随便改动，那么如果偶数列对奇数列大写字母数量影响的奇偶性符合我原本要消灭的大写字母的数量的奇偶性，我通过①操作显然就可以达到最终答案，反之永远不能。
偶数列也是一样。
我们这样就可以得到最终答案了。提示一点，输入数据要保证能表示成大小写字母的形式，否则你怎么改都不行，直接输出no。