Our friend Alice got stuck in a big chessboard. The chessboard has N rows and N columns. Some cells are black, and some cells are white and the remaining cells do not have any color. She can paint the cells which do not already have any color on it to black or white. But she can't repaint the cells which already have some color. If she can make the chessboard consistent, then she can escape the chessboard. A chessboard is consistent if all of its cells are colored and every pair of adjacent cells have different color.

Now you are given the initial configuration of the chessboard. Let's help Alice find out if she can escape the chessboard.

Input

In the first line of input, there will be a number T (1 ≤ T ≤ 50) denoting the number of test cases. T test cases follow.

The first line of each test case contains two space separated integers N(1 ≤ N ≤ 1018) and Q(0 ≤ Q ≤ 1000). Here the chessboard's size is NxN and Q cells are already colored. On the next Q lines, there will be three integers x, y, c. The y'th(1 ≤ y ≤ N) cell of the x'th(1 ≤ x ≤ N) row has color c(1 ≤ c ≤ 2). You can be sure that no cell will appear more than once in a test case.

Here color c can take two values: 1 represents the color black. 2 represents the color white.

Output

For each test case print a single line with yes or no.

If Alice can escape the chessboard, print yes for that corresponding test case. Otherwise, print no.