401740: GYM100519 L Linear Systems

After dealing with sociology problem last year, you now have some troubles with linear algebra.

An old professor likes to give his students huge systems of linear equations by prime modulo P to solve as a homework. He can dictate them for hours, but he found out that students still solve them quite fast and giving even bigger systems of linear equations is not an option due to limited duration of the seminar. He invented one feature though: he has his favorite number L, and if he has already dictated L coefficients of the equation, he can stop and instruct students to copy the other (N - L) coefficients from the the beginning of one of the previous equations, and then dictates the right part of the equation.

OK, you'll have to deal with the task of automating the solving of a system of linear equations given in that form.

On the first line of input, integers N, M, L and P are given, where N is the number of unknown variables, M is the number of equations, L is the favorite number of the professor and P is the number serving as a modulo (1 ≤ N, M ≤ 4000, 1 ≤ L < N, 2 ≤ P ≤ 10⁹, P is prime).

The next M lines contain the equation descriptions. The first integer denotes the type of the equation: 1 if the equation is defined by professor in complete form, or 2 if he referenced the previous equation in its definition. In the former case, the line then contains (N + 1) integers: the coefficients for the unknown variables and the right side of equation. In the latter case, the line then contains (L + 2) integers: the L coefficients for the unknown variables, the index n_i of the equation referenced by the professor (1 ≤ n_i < i) and the right side of equation. All coefficients are non-negative and less than P.

The total amount of coefficients for the unknown variables dictated by the professor is not greater than 10 000.

The first line of output must contain "No solution" if there is no solution for the given system of linear equations.

If a solution exists, then the first line of output must look like "There are P  k solutions", where k is the dimension of the solution space. The second line in this case must contain N integers x_i: the solution itself (0 ≤ x_i < P). If there are multiple solutions with these criteria, output the one with the minimal x₁. If there are still multiple solutions, output the one with the minimal x₂, and so on.

4 4 2 13
1 1 0 0 0 1
1 0 1 0 0 2
1 0 0 1 0 3
1 0 0 0 1 4

There are 13  0 solutions
1 2 3 4

4 3 1 19
1 1 0 0 0 1
2 1 1 2
2 1 2 3

There are 19  1 solutions
1 1 1 0

2 2 1 11
1 1 1 1
2 1 1 2

No solution