Participants in educational programs often wonder why there is usually a break of several days between two programs. The answer is simple: the Sirius staff needs to get the rooms in order after the previous program.

There are $n$ rooms in the Sirius educational center, numbered from $1$ to $n$. After an educational program, these rooms need renovation.

Renovation work involves $k$ employees, numbered from $1$ to $k$. Each $i$-th employee is assigned a range of room numbers from $l_i$ to $r_i$ inclusive, and a specific room $m_i$ within this range, from which they must start their inspection of these rooms. The ranges of rooms for different employees may overlap and even coincide.

Employees are sent from the base to perform work in some order. The next employee is sent only after the previous one returns to the base.

When the $i$-th employee is sent to perform work, they first go to room $m_i$. If this room still needs renovation, the employee renovates it, and also visits all other rooms in the range from $l_i$ to $r_i$ for which they are responsible, and renovates all rooms in this range that need renovation, after which they return to the base. After this, all rooms in the range from $l_i$ to $r_i$ no longer need renovation.

If the room $m_i$ visited by the employee does not need renovation, because it has already been renovated by a colleague sent earlier to perform work, the employee immediately returns to the base, hoping that colleagues have already renovated all other rooms in their range. In this case, some other rooms in the range from $l_i$ to $r_i$ may still need renovation.

Determine whether it is possible, with such an approach, to send employees to perform their duties in such an order that, in the end, all rooms from $1$ to $n$ are renovated.

Input

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. The following is a description of the test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n, k \le 5 \cdot 10^5$) — the number of rooms and the number of employees, respectively.

Each of the following $k$ lines contains three integers $l_i$, $m_i$, and $r_i$ ($1 \le l_i \le m_i \le r_i \le n$) — the first room of the range assigned to the $i$-th employee, the room in the range from which they must start their work, and the last room of their range, respectively.

It is guaranteed that the sum of $n$ and $k$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output "YES" if it is possible to renovate all rooms, and "NO" otherwise.

Examples

Input 1

2
5 2
3 4 5
1 3 3
5 3
1 2 4
2 4 5
3 3 3

Output 1

YES
NO

Note

In the first test case from the example, it is necessary to first send the second employee to perform renovation work; they will renovate rooms from the first to the third. Then the first employee is sent to room $4$. Since it still needs renovation, the first employee will renovate the remaining rooms in their range. As a result, all rooms will be renovated.

In the second test case, it is impossible to choose a suitable order for sending employees.