There are $n$ boxes placed on an infinitely long number line. The $i$-th box ($1 \le i \le n$) is at position $a_i$ on the number line at time $0$, and you want it to be at position $b_i$ at time $t_i$ and all subsequent times. It is guaranteed that the sequences $[a_1, \dots, a_n]$ and $[b_1, \dots, b_n]$ are strictly increasing.

To achieve this, in each unit of time starting from time $0$, you can move a box one unit length along the number line, or do nothing. You must ensure that at any moment, there is at most one box at any point. Formally, in each unit of time, you can perform one operation as follows, or perform no operation:

1. Choose any box. Let its index be $i$ and its current position be $p_i$.
2. Choose a direction $d \in \{ \pm 1 \}$, where $d = 1$ represents moving to the right and $d = -1$ represents moving to the left. You must ensure that there is no box at position $(p_i + d)$ on the number line.
3. Move box $i$ from point $p_i$ to point $(p_i + d)$.

You want to know if there exists a sequence of operations that satisfies the requirements for all boxes, i.e., for any $1 \le i \le n$, the $i$-th box is at position $b_i$ at time $t_i$ and all subsequent times.

Input

The first line contains two integers $c$ and $T$, representing the test case ID and the number of test cases, respectively.

For each test case, the first line contains an integer $n$, representing the number of boxes. The next $n$ lines each contain three integers $a_i, b_i, t_i$, representing the initial position, target position, and time requirement for the $i$-th box, respectively.

Output

For each test case, output a single line containing the string "Yes" or "No", indicating whether there exists a sequence of operations that satisfies the requirements for all boxes simultaneously.

Constraints

For all test cases: $1 \le T \le 6$ $1 \le n \le 2 \times 10^5$ $\forall 1 \le i \le n, 1 \le a_i, b_i \le 10^9, 0 \le t_i \le 10^{16}$ $\forall 1 \le i < n, a_i < a_{i+1}, b_i < b_{i+1}$

Special Property A: $\forall 1 \le i < j \le n, t_i = t_j$. Special Property B: $\forall 1 \le i \le n, a_i \le b_i$ and $\forall 1 \le i < n, b_i < a_{i+1}$. Special Property C: $\forall 1 \le i \le n, a_i \le b_i$.

Examples

Input 1

1 0
2
2 2
4 5 1
6 7 1
3
4 5 3
7 6 1
10 8 4

Output 1

No
Yes

Note

The first test case is impossible. Moving box 1 from 4 to 5 and box 2 from 6 to 7 requires at least two units of time, so they cannot both reach their targets at time 1.

The second test case is possible: - From time 0 to 1, move box 2 from 7 to 6. - From time 1 to 2, move box 3 from 10 to 9. - From time 2 to 3, move box 1 from 4 to 5. - From time 3 to 4, move box 3 from 9 to 8. - From time 4 onwards, do nothing.

Input 2

2 6
(See move/move2.in)

Output 2

(See move/move2.ans)

Input 3

3 6
(See move/move3.in)

Output 3

(See move/move3.ans)

Input 4

4 6
(See move/move4.in)

Output 4

(See move/move4.ans)

Input 5

5 6
(See move/move5.in)

Output 5

(See move/move5.ans)