小 Roman 正在研究线性同余发生器（Linear Congruential Generator，简称 LCG），这是最古老且最著名的伪随机数生成算法之一。线性同余发生器从一个非负整数 $x_0$（也称为种子）开始，生成一个非负整数序列 $x_i$（$0 \le x_i < c$），其递推关系如下：

$$x_{i+1} = (ax_i + b) \pmod c$$

其中 $a, b, c$ 为非负整数，且 $0 \le x_0 < c$。

Roman 对不同 LCG 生成的序列之间的关系很感兴趣。具体来说，他有 $n$ 个不同的 LCG，参数分别为 $a^{(j)}, b^{(j)}$ 和 $c^{(j)}$（$1 \le j \le n$），其中第 $j$ 个 LCG 生成序列 $x_i^{(j)}$。他希望从每个 LCG 生成的序列中各取出一个数，使得这些数的和最大，且该和不能被给定的整数 $k$ 整除。

形式化地，Roman 想要找到整数 $t_j \ge 0$（$1 \le j \le n$），以最大化 $s = \sum_{j=1}^n x_{t_j}^{(j)}$，并满足约束条件 $s \pmod k \neq 0$。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10\,000$，$1 \le k \le 10^9$）。

接下来的 $n$ 行描述各个 LCG。每行包含四个整数 $x_0^{(j)}, a^{(j)}, b^{(j)}$ 和 $c^{(j)}$（$0 \le a^{(j)}, b^{(j)} \le 1000$，$0 \le x_0^{(j)} < c^{(j)} \le 1000$）。

输出格式

如果 Roman 的问题有解，则在输出文件的第一行输出一个整数 $s$——即不能被 $k$ 整除的最大和，并在下一行输出 $n$ 个整数 $t_j$（$0 \le t_j \le 10^9$），表示该和对应的一组解。

否则，输出一行包含数字 $-1$。

样例

样例输入 1

2 3
1 1 1 6
2 4 0 5

样例输出 1

8
4 1

样例输入 2

2 2
0 7 2 8
2 5 0 6

样例输出 2

-1

说明

在第一个样例中，一个 LCG 生成的序列为 $1, 2, 3, 4, 5, 0, 1, 2, \dots$，而另一个 LCG 生成的序列为 $2, 3, 2, 3, 2, \dots$。

在第二个样例中，一个 LCG 生成的序列为 $0, 2, 0, 2, 0, \dots$，而另一个 LCG 生成的序列为 $2, 4, 2, 4, 2, \dots$。