#P10755. 世界大战
世界大战
题目描述
两人在一个 的棋盘上进行游戏。每格的士兵属于同盟国或轴心国,分别用 、 表示。Nick 先手,随后两人交替操作。
一次操作选取一个矩形 到 ,其中 ,。必须保证右下角 当前是 。将上边界和下边界上所有格子的阵营反转,即 与 互换。若 ,同一排只反转一次。
棋盘上没有 时,轮到操作的玩家输。双方都采取最优策略,判断谁获胜。
输入格式
第一行一个正整数 。每组先输入两个整数 ,接下来 行,每行一个长度为 的二进制串。
输出格式
每组输出一行。若 Nick 获胜,输出 N,否则输出 C。
样例 1
2
2 2
01
10
3 3
111
101
111
C
N
样例 2
2
1 3
111
3 1
1
1
1
N
C
数据范围
- 的数据满足 。
- 的数据满足 。
- 另外 的数据满足 。
- 所有数据满足 ,。