Description

[If you do not want to read the story, please read the part below the separator.]

Xiao L and Xiao K are the leaders of two gangs, and they are sworn enemies. One year, a large-scale conflict broke out between the two gangs. Xiao K, being weaker, was surrounded by Xiao L’s followers and was finally forced to retreat to a large shooting range. Xiao K knew the situation was hopeless. Just as he was about to fight Xiao L to the death, news came that Xiao L wanted to invite him to play a game. Xiao K knew there must be a trap, but he had no other choice, so he went alone to the meeting point Xiao L specified.

The meeting point was beside the shooting range. Xiao L stood in the field and waved to the approaching Xiao K with a smile. “Ah, Xiao K, long time no see. I remember the last time we met, it was in that small tavern. Back then, I chatted with you happily and talked about the world. Who would have thought we would end up like this today!” Xiao L paused and continued, “You used to be my brother. I do not want to end things between us with violence. Luckily, I have a good idea: how about we settle this with a game? What do you say, Xiao K?” Xiao K knew he had no room to refuse Xiao L, so he nodded. Seeing that, Xiao L smiled again and began to explain the rules of the game.

“As you can see, our game will be played on this shooting range. The range has a total of $n$ rows and $m$ columns, i.e. $n\times m$ targets. For convenience, let the row direction be left to right, and the column direction be front to back. This shooting range has a special feature: each target has a counter. If you hit a target, the displayed value of its counter increases by one. However, each counter value has a range: it can only be an integer not less than $0$ and not greater than $k$. If you hit a target when its counter value is already $k$ before the hit, then upon being hit, its counter overflows, resets to $0$, and emits an overflow error signal that starts to travel along wires. Due to the special wiring of the range, the signal only travels to the right. During the transmission, it affects some other counters in the same row. If an affected counter has value $k$, it will also overflow, reset to $0$, and emit an overflow error signal, which stacks with the previous signal (but the $+1$ effect does not stack). Otherwise, its value increases by one, and it sends a correction message that cuts off the signal propagation, meaning targets to its right will no longer be affected. Of course, if the signal keeps traveling without being cut off, it will eventually reach the information management terminal. Because signals keep stacking during transmission, and because the terminal has to process huge amounts of information, its ability to correct error signals is weak; this may cause the terminal to crash or even explode, which is against the rules.

“You and I will take turns choosing one target to shoot once. The shooter decides which target to shoot. If it is someone’s turn to shoot but they cannot make a shot without breaking the rules, then they lose. Since I designed this game, I will go first. However, I will also give you some choices. The initial value of each target’s counter is not necessarily $0$; I can set it. I happen to have several setting plans, but I do not know which one to choose. Could you help me pick one?”

Xiao L took a few slips of paper out of his pocket. Xiao K looked and found that each slip did not list the initial values of all counters; it only had three numbers $a,b,c$. What Xiao L did not know was that Xiao K had amazing observation skills. While Xiao L was speaking, Xiao K had already analyzed how the displayed values changed and how the circuit was wired, and figured out the rule used to generate the initial counter values. The initial values of the counters are generated one by one in order. The order is row-major: from left to right, from top to bottom. Specifically, they are generated in the order of row $1$ column $1,2,\ldots,m$, then row $2$ column $1,2,\ldots,m$, ..., up to row $n$ column $1,2,\ldots,m$. Generating one counter value uses $a,b,c$ as parameters, and after each generation, $a,b,c$ all change. Concretely, for each generated counter value, the following function is called once:

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);
}

The return value of the function is the generated counter value. It is easy to see that all initial values are integers between $0$ and $k$, so they do not violate the rules.

Xiao K knows Xiao L is extremely smart and will surely aim to win. Of course, since Xiao K also knows a lot about this game, his skill will not be worse than Xiao L’s. Xiao K cannot break the rules made by Xiao L, or he might anger Xiao L and cause the conflict to break out again. However, Xiao K can compute which of Xiao L’s plans guarantee a win for Xiao L, and which guarantee a win for himself, and then choose a plan where he is guaranteed to win.

Unfortunately, time does not allow Xiao K to compute for too long. Luckily, you can program and help Xiao K get the result in a short time. Please help Xiao K determine, among all the plans Xiao L provides, which ones make Xiao L sure to win and which ones make Xiao L sure to lose.

Since what Xiao L said may be too long to understand, Xiao K decides to describe the problem more concisely. Xiao L provides a number matrix with $n$ rows and $m$ columns. Xiao L and Xiao K take turns operating. Each time, one number in the matrix can be increased by $1$. If after adding $1$ this number becomes greater than $k$, then it is reset to zero, and the $+1$ operation is passed to the number on its right. If a number needs to pass the operation but there is no number to its right, then the current player’s initial operation is not allowed. The player who cannot make a move loses. Xiao L moves first, and both players are extremely smart. If Xiao L will win, output YES; otherwise output NO.

The initial numbers in the matrix are provided by Xiao L. Xiao L provides several plans to fill the matrix; in each plan, the numbers in the matrix are generated by the function above, in order from left to right and from top to bottom. The difference between plans lies in different parameters $a,b,c$. It is guaranteed that the generation method is irrelevant to the correct solution of this problem. Note that for each plan, Xiao L actually provides six parameters $k,n,m,a,b,c$, meaning $k,n,m$ may also differ between plans.

Input Format

The first line contains the total number of plans provided by Xiao L.

For each plan, six parameters are given in order: $k,n,m,a,b,c$, with meanings as described in the statement.

Output Format

For each plan, if Xiao L will win, output YES; otherwise output NO.

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

YES
NO

Hint

[Sample Explanation]

In both plans, there is only one target in the shooting range.

For plan 1, the initial value on this target’s counter is $0$. Xiao L, as the first player, shoots this target and makes its counter increase by $1$. When it is Xiao K’s turn, the counter value is $1$, and there is no legal shot, so Xiao K loses and Xiao L wins.

For plan 2, the initial value on this target’s counter is $1$, and there is no legal shot, so Xiao L loses.

[Constraints]

At most $20$ plans.

For all testdata, $k,n,m,a,b,c$ are positive integers, and $1\le a,b,c\le10^{18}$. The score distribution is as follows: test ID $1$ is worth $7$ points; test IDs $9$, $12$, and $15$ are worth $5$ points; all others are worth $6$ points.

Translated by ChatGPT 5