Chain Reaction Shooting Game

Two rival leaders, L and K, play a deadly game on a shooting range. The shooting range is organized as an n×m grid of targets. Each target has a counter whose value is an integer in the range (0) to (k). When a target is hit, its counter is increased by 1. However, if the counter was already at (k), it resets to (0) and an overflow signal is generated that is transmitted to the target immediately to its right in the same row. This transmission follows the same rule: if the receiving target’s counter is (k), it too resets to (0) and the signal is passed further to its right; otherwise the counter is simply incremented and the signal ends. If at any point a signal must be passed to a non‐existent target (i.e. there is no target to the right), then the very first shot that initiated this chain is deemed illegal and cannot be played.

The game is played by two players – L (the first mover) and K – who take turns. On a turn, a player picks any target in the grid and “shoots” it. The shot is legal only if the ensuing chain reaction (if any) does not require passing the signal off the right end of the row. If a player on his turn has no legal moves, he loses.

Before the game starts, L announces one or more schemes for filling the grid with initial counter values. The values are generated by a pseudo‐random generator. For each scheme, L provides 6 parameters: (k, n, m, a, b, c). The grid is filled in row–major order (from left to right, top to bottom) by repeatedly invoking the function below. In each call the parameters (a, b, c) are updated. (Note that the way the grid is generated has no effect on the correct solution.)

The pseudo–random generator is defined as follows (in C/C++ style):

[ \begin{array}{l} // Type: unsigned long long 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);
} ]

For each generated grid (of size (n) rows and (m) columns), one can view every row as representing an integer in base (k+1). In a row the first (left‐most) target is analogous to the least–significant digit. A legal shot in a row is equivalent to adding one of a prescribed set of values to that integer – the addition is performed with carrying (where a carry resets a digit to 0) and a move is legal only if no carry “falls off” the right end of the row. In other words, if we define (b = k+1) and let the row’s integer value be (x = d_1 + d_2 \cdot b + \cdots + d_m \cdot b^{m-1}), then a shot on the target in column (j) is legal if (d_j, d_{j+1}, \ldots, d_m) are not all equal to (k). Such a shot adds (b^{j-1}) to (x) (with the usual carrying and digit–resetting), and the row reaches the terminal state when (x = b^m - 1\n

Finally, the game is the disjunctive sum (in the sense of combinatorial game theory) of the games on each row. Both players play optimally. Your task is: given a grid–filling scheme, decide whether L (the first mover) wins (output “YES”) or loses (output “NO”).

inputFormat

The input begins with an integer (T) (the number of test cases). Each test case consists of one line with six space–separated integers: (k, n, m, a, b, c). These parameters are used both for the game (where the counters range from (0) to (k) and the grid has (n) rows and (m) columns) and to generate the initial grid values as described above.

outputFormat

For each test case, output a single line containing “YES” if L (the first mover) can force a win, or “NO” otherwise.

sample

1
1 1 1 1 1 1

YES