题目描述

【如果不想看题面请阅读分割线以下部分】

小 L 与小 K 是两个帮派的首领，也是死敌。某年某月，两个帮派发生了大规模的冲突。小 K 因为实力不敌，被小 L 的爪牙团团包围，最终被逼近了一个大型射击场。小 K 自知大势已去，正准备与小 L 拼死一战时，却传来消息，说小 L 要邀请自己与他来玩一场游戏。小 K 知道其中有鬼，但却别无它计，只能只身前往小 L 指定的会面点。

会面点在射击场旁。小 L 站在场上，满脸笑容地对走来的小 K 招手。“啊，小 K ，好久不见。我记得上次我们见面的时候，还是在那个小酒馆。当时，我与你谈笑风生，指点江山，不亦乐乎。没想到，如今，我们竟到此地步啊！”小 L 顿了顿，继续说道：“你是我曾经的兄弟，我不想以暴力的方式了解你我。正好，我有一个好方法：不如我们用游戏的方式来场决战吧！这样如何，小 K ？”小 K 知道，自己并没有否定小 L 的余地。于是，小 K 点了点头。小 L 看到小 K 点头，又露出了笑容，开始讲起了游戏的规则。

“如你所见，我们的游戏要在这片射击场上进行。射击场总共有 $n$ 行 $m$ 列，共 $n\times m$ 个靶。为了方便，取行的方向为左右，列的方向为前后。这个射击场有一个特点：每个靶上都有一个计数器。击中一个靶，这个靶的计数器示数就会加一。但是，每个靶的示数有一个范围，只能是不小于 $0$，不大于 $k$ 的整数。倘若击中一个靶，而在未击中此靶前此靶计数器的示数已经为 $k$，那么击中时，此靶计数器示数就会溢出清 $0$，并产生溢出错误的信号，经电线开始传递。由于靶场电线的特殊布置，信号只会往右侧传递。信号传递过程中会影响若干其它同行靶的计数器。如果这些被影响到的靶计数器示数为 $k$，其同样会溢出清 $0$ 并产生溢出错误信号，与之前的信号叠加（但加一效果不会叠加）；否则，其示数会加一，并发出纠正讯息，截断信号传播，即在其右侧的靶不会继续被信号影响。当然，如果信号一直传递而未被截断，那么它最终会传入信息管理终端。由于信号在传递过程中不断叠加，再加之信息管理终端要处理庞大的信息，纠正错误信号的能力较差，可能会导致终端死机甚至发生爆炸的危险，这是违规的。

“我与你会轮流选择其中一个靶进行一次射击，射击哪个靶由射击者自行决定。如果轮到某个人射击，但他无法进行不违规的射击，那么他就输了。因为这是我设计的游戏，先手当然是我。但是，我也会给你一些选择。靶场上每个靶计数器的初始示数不一定为 $0$，是可以被我设置的。我这里恰好有几种设置方案，但我不知道该选哪种好，可否请你帮我选一选？”

小 L 从口袋里抽出了几张纸条。小 K 一看，每张纸条却没有写每个靶计数器的初始示数，只写着三个数字 $a,b,c$。小 L 所不知道的是，小 K 有着惊人的观察能力，在小 L 讲刚才那一番话之时，小 K 就已经通过分析靶上示数的变化以及电路的布置，得出了计数器初始示数生成的规律。靶场上靶的计数器初始示数是一个个按顺序生成的。并且，生成的顺序是按行优先，从左到右，从上到下。具体来说，是按照第 $1$ 行第 $1,2,\ldots ,m$ 个，第 $2$ 行第 $1,2,\ldots ,m$ 个，……，第 $n$ 行第 $1,2,\ldots ,m$ 个的顺序生成。生成一个计数器的示数需要用到 $a,b,c$ 作为参数。并且，每生成一个计数器的示数，$a,b,c$ 都会产生变化。具体来说，每生成一个计数器的示数，便引用一次以下的函数：

typedef unsigned long long ull; 
inline ull generate(ull&a,ull&b,ull&c,ull&k)
{ 
	a<<=19;a+=b+c;
	a<<=26;a^=c+=a+81;b--;
	a<<=7;a>>=(b^c^1145)&14;
	c*=a;a|=b+=c;a^=b&c;
	return a%(k+1);
}

函数的返回值即为生成的计数器示数。容易发现，初始示数均为不小于 $0$，不大于 $k$ 的整数，不违反规则。

小 K 知道小 L 是绝顶聪明的人，且一定会以自己的胜利为目标进行游戏。当然，小 K 因为掌握了许多这个游戏的信息，水平不会落后于小 L。小 K 不能违反小 L 制定的规则，否则可能惹恼小 L，使冲突再次爆发。但是，小 K 可以通过计算，得出小 L 给出的方案中哪些是小 L 必胜，哪些是自己必胜的，并选择一个自己必胜的方案进行游戏。

可惜时间不允许小 K 做太长时间的计算。恰好，会编程的你可以帮助小 K 在较短的时间内得出结果。请你帮小 K 算算，在小 L 给出的所有方案中，哪些小 L 必胜，哪些小 L 必败。

---

考虑到小 L 说的话可能太长以至于难以理解，小 K 决定更为简洁地叙述这个问题。小 L 提供了一个 $n$ 行 $m$ 列的数阵。小 L 与小 K 二人轮流操作，每次可以将数阵中的某个数加上 $1$。若加 $1$ 后此数大于 $k$，则此数清零，将加 $1$ 操作传递给其右侧的数。若某个数需要传递操作，但其右侧没有数，则这个操作对应的人的初始操作将不可进行。最后无法操作的人败。小 L 为先手，二人都绝顶聪明。若小 L 会赢则输出 YES，否则输出 NO。

数阵里初始的数由小 L 提供。小 L 提供了若干个填充数阵的方案，每个方案中数阵里的数由上文的函数生成，生成顺序从左到右，从上到下。方案的互异性体现在参数 $a,b,c$ 的不同。请你对每种方案给出答案。 保证生成方式与题目的正确解法无关。 注意对于每种方案，小 L 实际上提供了六个参数 $k,n,m,a,b,c$，即 $k,n,m$ 在每种方案中也可能各不相同。

输入格式

第一行为小 L 给出方案总数。

对于每种方案，按顺序给出六个参数：$k,n,m,a,b,c$，其意义如题所示。

输出格式

对于每种方案，如果小 L 会赢，输出 YES，否则输出 NO。

2
1 1 1 1 1 1
1 1 1 2 2 2

YES
NO

提示

【样例解释】

两种方案中射击场上都只有一个靶。

对于方案一，此靶计数器上的初始数值为 $0$。小 L 先手射击此靶使其计数器加 $1$。轮到小 K 时，计数器示数为 $1$，不存在不违规射击方案，小 K 输，小 L 赢。

对于方案二，此靶计数器上的初始数值为 $1$，不存在不违规射击方案，小 L 输。

【数据范围】

最多 $20$ 种方案。

数据编号	$n$ 的范围	$m$ 的范围	$k$ 的范围	特殊性质
$1$	$n=1$	$1\le m\le5$	$1\le k\le 5$	无
$2$		$1\le m\le20$
$3$		$1\le m\le100000$	$1\le k\le 10^{18}$
$4$	$1\le n \le2$
$5$	$1\le n \le100000$	$m=1$
$6$	$1\le n \le1000$	$1\le m\le1000$		$k$为偶数
$7$	$1\le n \le50000$	$1\le m\le20$
$8$	$1\le n \le10$	$1\le m\le100000$
$9\sim 11$	$1\le n \le1000$	$1\le m\le1000$		无
$12\sim 14$	$1\le n \le50000$	$1\le m\le20$
$15\sim 17$	$1\le n \le10$	$1\le m\le100000$

对于所有数据，$k,n,m,a,b,c$ 均为正整数，$1\le a,b,c\le10^{18}$。各数据点分值分布如下：编号为 $1$ 的数据点分值为 $7$；编号为 $9$、$12$、$15$ 的数据点分值为 $5$；其余数据点分值为 $6$。