题目描述

罗曼在学习线性同余发生器——最古老，也是最广为人知的伪随机数生成算法之一。线性同余发生器（LCG）以 $x_0$ 为随机种子，生成很多非负整数 $x_i$ ,它遵循以下规则：

给定非负整数 $a,b,c\space(0≤x_0<c)$ ， $x_{i+1} = (ax_i+b)\space mod \space c$

罗曼很好奇由不同LCG产生的序列之间的关系。特别地，他有 $n$ 个不同的LCG，含有参数 $a^{(j)}, b^{(j)}, c^{(j)}\space(1≤j≤n)$。第 $j$ 个LCG会生成一个序列 $x_i^{(j)}$ 。

他希望能从每个LCG产生的序列中挑出一个数，使他们的和最大，且不被给定的 $k$ 整除。

格式化一点来说，他希望找到整数 $t_j \space(t_j>0,1≤j≤n)$ ，使$s=\sum\limits_{j=1}^nx_{t_j}^{(j)}$最大，且$s\not\equiv0(mod\space k)$。

输入格式

第 $1$ 行包括两个整数$n,k$。

$(1≤n≤10000,1≤k≤10^9)$

接下来 $n$ 行描述LCG，每行包括4个整数：$x_0^{(j)},a^{(j)}, b^{(j)}, c^{(j)}$ 。

$(0≤a^{(j)}, b^{(j)}≤1000,0≤x_0^{(j)}<c^{(j)}≤1000)$

输出格式

如果有解，第 $1$ 行输出 $s$，第 $2$ 行输出 $n$ 个 $t_j$ 。

$(0≤t_j≤10^9)$ 。

如果无解，输出 $-1$ 。

2 3
1 1 1 6
2 4 0 5

8
4 1

2 2
0 7 2 8
2 5 0 6

-1

提示

时间限制：1秒

空间限制：256MB