NONNEG

Let ~A~ be an ~N \times N~ square matrix. The elements of the matrix are either integer numbers (positive or negative) or the special value ~\infty~ (infinity). We know that in each row of the matrix, there are at most ~13~ elements that contain numbers - for brevity, we will call them "numeric elements."

We play the following game: In each move, we first choose a number ~K~ (where ~1 \le K \le N~) and an integer number ~X~, and then:

• we add ~X~ to all numeric elements in the ~K~-th row of ~A~, and
• we subtract ~X~ from all numeric elements in the ~K~-th column of ~A~.

We win the game if we find a sequence of moves that, when executed sequentially, result in all numeric elements of the matrix containing non-negative values.

Input Data

The first line of the input will contain two natural numbers ~T~ and ~N~, separated by a single space. The first one will indicate the number of matrices to follow, and the second one the dimension of the matrices. The next ~T \times N~ lines of the input will give consecutively the elements of ~T~ matrices ~A_1, A_2, ..., A_T~ as follows: lines from ~2~ to ~N + 1~ will correspond to matrix ~A_1~, lines from ~N + 2~ to ~2 \times N + 1~ will correspond to matrix ~A_2~, etc. The input line corresponding to the ~i~-th row of matrix ~A_k~ will first contain a number ~M_i~, representing the number of numeric elements in the row (~0 \le M_i \le 13~). Then, it will contain ~M_i~ pairs of numbers ~j~, ~v~, each one indicating that the element ~A_k[i, j]~ of the matrix contains the value ~v~. It will hold that ~1 \le j \le N~ and ~|v| \le 10^6~. Numbers in each line will be separated in pairs by a single space.

Output Data

The output should consist of ~T~ lines, each containing one of the words "true" or "false". The ~k~-th line of the output should contain "true" if and only if there exists a sequence of moves that wins the game for matrix ~A_k~.

Constraints

~1 \le T \le 10~
~2 \le N \le 1.000~
Execution time limit: 1 sec.
Memory limit: 64 MB.

Example of Input - Output

STDIN (nonneg.in)

2 4
2 1 8 3 -2
2 2 2 3 5
2 2 0 4 4
2 1 -1 3 7
2 2 -1 4 -1
0
2 2 9 4 -2
1 1 0

STDOUT (nonneg.out)

true
false

$$\displaystyle A_1 = \begin{bmatrix} 8& \infty & -2 &\infty\\ \infty & 2 & 5 & \infty\\ \infty & 0 & \infty & 4\\ -1 &\infty &7 &\infty \end{bmatrix} \; A_2 = \begin{bmatrix} \infty& -1 & \infty &-1\\ \infty & \infty & \infty & \infty\\ \infty & 9 & \infty & -2\\ 0 &\infty &\infty &\infty \end{bmatrix} $$

Explanation of the Example: The example contains the two matrices, ~A_1~ and ~A_2~, given above. For ~A_1~, we can win the game, for example, with the sequence of moves [~(1,\;2)~, ~(4,\;3)~]. On the contrary, for ~A_2~, it is not possible to win the game with any sequence of moves. (Try it!)