在去年解决了社会学问题之后，你现在在高等代数上遇到了一些麻烦。

一位老教授喜欢给他的学生们留一些巨大的模素数 $P$ 的线性方程组作为家庭作业。他可以连续口授几个小时，但他发现学生们仍然能很快地解决它们，而由于研讨会时间有限，给出更大的线性方程组并不是一个可行的选择。不过，他发明了一个新花样：他有一个最喜欢的数字 $L$。如果他已经口授了方程的前 $L$ 个系数，他就可以停下来，指示学生从之前某个方程的开头复制其余的 $(N - L)$ 个系数，然后再口授方程的右侧常数项。

好吧，你必须解决这个任务：自动求解以这种形式给出的线性方程组。

输入格式

输入的第一行给出整数 $N, M, L$ 和 $P$，其中 $N$ 是未知数的个数，$M$ 是方程的个数，$L$ 是教授最喜欢的数字，$P$ 是模数（$1 \le N, M \le 4000$，$1 \le L < N$，$2 \le P \le 10^9$，$P$ 为素数）。

接下来的 $M$ 行包含方程的描述。第一个整数表示方程的类型：如果为 $1$，表示该方程由教授以完整形式定义；如果为 $2$，表示他在定义中引用了之前的方程。

• 在前一种情况下，该行随后包含 $(N + 1)$ 个整数：未知数的系数和方程的右侧常数项。
• 在后一种情况下，该行随后包含 $(L + 2)$ 个整数：前 $L$ 个未知数的系数、教授所引用的方程的索引 $n_i$（$1 \le n_i < i$）以及方程的右侧常数项。

所有系数均为非负且小于 $P$。

教授口授的未知数系数的总数不超过 $10\,000$。

输出格式

如果给定的线性方程组无解，输出的第一行必须包含 No solution。

如果存在解，则输出的第一行必须形如 There are P ^ k solutions，其中 $P$ 为模数的值，$k$ 是解空间的维数。在这种情况下，第二行必须包含 $N$ 个整数 $x_i$：即解本身（$0 \le x_i < P$）。如果在此标准下有多个解，输出使得 $x_1$ 最小的那个。如果仍有多个解，输出使得 $x_2$ 最小的那个，依此类推。

样例

输入样例 1

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

输出样例 1

There are 13 ^ 0 solutions
1 2 3 4

输入样例 2

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

输出样例 2

There are 19 ^ 1 solutions
1 1 1 0

输入样例 3

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

输出样例 3

No solution