Consider the following constraint satisfaction problem. You are given n vari- ables x1, x2, . . . , xn and a set of m two-variable linear constraints. Each con- straint takes the form axi + bxj = 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. Input 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 ≤ 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 ≤ i,j ≤ n and 0 ≤ |a|,|b|,|c| ≤ 10,000,000. Output For each test case, output one line containing ‘yes’ if all constraints are satisfiable and ‘no’ otherwise. Sample Input 2 2 1 10 31625 2 1 10 31629 Sample Output no yes