Linear Equations#7208
Sign in

Linear Equations

1 second
64 megabytes
Easy

Create a program that solves a system of linear equations with integer coefficients in variables:

a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + \cdots + a_{1m}x_m = a_{1(m+1)};\\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + \cdots + a_{2m}x_m = a_{2(m+1)};\\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + \cdots + a_{3m}x_m = a_{3(m+1)};\\ \vdots\\ a_{n1}x_1 + a_{n2}x_2 + a_{n3}x_3 + \cdots + a_{nm}x_m = a_{n(m+1)}.

Input

The first line contains the natural numbers and . For from to , line (j+1) contains a sequence of integer coefficients a_{jk}, separated by spaces, in increasing order of from to m + 1. It is guaranteed that (m+1)n \leq 8000, and |a_{jk}| \leq 1234567890 for all coefficients.

Output

If the system is inconsistent, output a single line starting with No solution.

If the system has a unique solution, output a single line with the values x_j in increasing order of from to .

If the system has infinitely many solutions, then for each from to , output a line with the coefficients of the -th equation of the system obtained after applying the method of successive variable elimination—there should be (m + 1) values per line.

In cases 2–3, the output line begins with a space, followed by the first number, space, second number, space, and so on. All numbers must be presented as irreducible fractions (numerator is integer, denominator is natural; if the denominator is , do not include the slash "/" or denominator). For this problem, you do not need to represent integers as arrays of their digits.

Examples

Example 1

Loading
Loading