Problem A: Satisfying Constraints

Consider the following constraint satisfaction problem. You are given n variables x₁, x₂, ..., x_n and a set of m two-variable linear constraints. Each constraint takes the form ax_i + bx_j = c where a, b, and c are integer constants. Each variable is allowed to take an integer value between 1 and k for some specified constant k.

Your goal is to determine if it is possible to assign an integer value in the valid range to each variable such that all constraints are satisfied.

The number of test cases is given in the first line of the input. Each test case begins with a line containing integers n, m, and k where 1 ≤ n ≤ 1000 is the number of variables, 0 ≤ m &le 10,000 is the number of constraints and 1 ≤ k ≤ 100 is the largest value allowed for the variable assignments. The following m lines each contain 5 integers a,i,b,j, and c where 1 &le i,j ≤ n and 0 &le |a|,|b|,|c| ≤ 10,000,000.

For each test case, output one line containing yes if all constraints are satisfiable and no otherwise.

Sample input

2
2 1 10
3 1 6 2 5
2 1 10
3 1 6 2 9

Output for sample input

no
yes