Bạn được cho \(n\cdot(m+1)\) hệ số \(a_{i,j}\) và \(b_i\), tạo thành \(n\) phương trình tuyến tính sau:

• \(a_{1,1}x_1 + a_{1,2}x_2 + \dots + a_{1,m}x_m = b_1 \pmod {10^9 + 7}\)

• \(a_{2,1}x_1 + a_{2,2}x_2 + \dots + a_{2,m}x_m = b_2 \pmod {10^9 + 7}\)

• \(\dots\)

• \(a_{n,1}x_1 + a_{n,2}x_2 + \dots + a_{n,m}x_m = b_n \pmod {10^9 + 7}\)

Nhiệm vụ của bạn là tìm bất kỳ \(m\) số nguyên \(x_1, x_2, \dots, x_m\) nào thỏa mãn các phương trình đã cho.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số phương trình và số biến.

\(n\) dòng tiếp theo, mỗi dòng chứa \(m+1\) số nguyên \(a_{i,1}, a_{i,2}, \dots, a_{i,m}, b_i\): các hệ số của phương trình thứ \(i\).

Output

In ra \(m\) số nguyên \(x_1, x_2,\dots, x_m\): giá trị của các biến thỏa mãn các phương trình. Các giá trị cũng phải thỏa mãn \(0 \le x_i < 10^9 + 7\). Bạn có thể in ra bất kỳ nghiệm hợp lệ nào. Nếu không tồn tại nghiệm, chỉ in ra \(-1\).

Constraints

• \(1 \le n, m \le 500\)

• \(0 \le a_{i,j}, b_i < 10^9 + 7\)

Example

3 3
2 0 1 7
1 2 0 0
1 3 1 2

2 1000000006 3