Description

$\text{Alice}$ and $\text{Bob}$ are playing a game called “Reversi”. The rules are as follows.

• The game is played on the Cartesian coordinate plane.

• $\text{Alice}$ uses black pieces, and $\text{Bob}$ uses white pieces.

• Initially, choose any $n$ lines parallel to the $X$ axis on the coordinate plane. Their intercepts on the $Y$ axis are all integers and are pairwise distinct. On each line, $\text{Alice}$ places one black piece, and $\text{Bob}$ places one white piece. The $X$ coordinates of all pieces are integers. The two pieces on the same line are not at the same position.

• $\text{Alice}$ and $\text{Bob}$ take turns to move, and $\text{Alice}$ always moves first. On each turn, a player first chooses a line, then moves their own-colored piece on that line along the line.

• A player may move their piece several integer units in one move toward the opponent’s piece; this is called forward. A player may also move their piece several integer units in one move away from the opponent’s piece; this is called backward.
  As long as a forward move does not pass over the opponent’s piece and does not make the black and white pieces overlap, there is no limit on how far the piece can move forward. However, the forward distance must be at least $1$. If the above conditions cannot be satisfied, the player cannot make a forward move.
  To avoid the game never ending due to repeated backward moves, in a single game, the total number of backward moves performed by a player cannot exceed $k$. Meanwhile, to prevent the game area from becoming too large and inconvenient to display, the distance of each backward move must be at least $1$ and at most $d$. If the above conditions cannot be satisfied, the player cannot make a backward move.

• When it is a player’s turn, if they can make a move, they must make exactly one move. This move can be a forward move or a backward move (if the limit on the number of backward moves has not been exceeded).

• If a player cannot make any move to move their piece, they lose and the game ends.

Given the initial state of the game, assuming that $\text{Alice}$ and $\text{Bob}$ both play optimally, determine whether $\text{Alice}$ can win.

Input Format

The input contains multiple test cases.

The first line contains an integer $T$, the number of test cases. Then there is a blank line. Next are $T$ test cases describing the initial states.

For each test case, the first line contains three integers $n$, $k$, $d$, representing the number of lines, the total allowed number of backward moves, and the maximum distance of each backward move. Then follow $n$ lines, each containing three integers $y_i$, $b_i$, $w_i$, representing the $Y$ intercept of the $i$-th line, and the $X$ coordinates of the black piece and the white piece on that line, respectively ($b_i \ne w_i$).

There is a blank line between every two test cases.

Output Format

If $\text{Alice}$ can win, output Yes; otherwise output No.

2

2 0 10
3 4 8
7 7 5

3 5 15
-3 -9 -19
-7 10 21
12 12 16

Yes
No

Hint

Sample Explanation

The figure below corresponds to the first test case of Input #1. If $\text{Alice}$ uses an optimal strategy, no matter how $\text{Bob}$ moves, $\text{Alice}$ can win.

Below is $\text{Alice}$’s winning strategy. First, $\text{Alice}$ chooses the line $y=3$ and moves the black piece from 4 to 6, so that the distance between the black and white pieces on both lines becomes $2$. Since $k$ is $0$, backward moves are essentially not allowed. If $\text{Bob}$ chooses to move the white piece on the line $y=3$, then the two pieces on that line will become adjacent and cannot be moved afterward. Similarly, if $\text{Bob}$ chooses to move the white piece on the line $y=7$, the two pieces on that line will also become adjacent and cannot be moved afterward. Therefore, no matter what $\text{Bob}$ does, one line will always end up with two adjacent pieces that cannot be moved anymore, while on the other line the distance between the pieces is $2$ and can still be moved once. $\text{Alice}$ then moves the remaining movable black piece by one more step. After that, $\text{Bob}$ cannot move any white piece, so $\text{Alice}$ wins.

For the second test case of Input #1, no matter how $\text{Alice}$ moves, $\text{Bob}$ can always win.

Constraints

For $100\%$ of the testdata, $1 \le T \le 100$, $1 \le n \le 100$, $0 \le k \le 100$, $1 \le d \le 20$, $-100 \le y_i \le 100$, $-10^3 \le b_i \le 10^3$, $-10^3 \le w_i \le 10^3$.

Translated by ChatGPT 5