P6979 [NEERC 2015] Generators

罗曼在学习线性同余发生器——最古老，也是最广为人知的伪随机数生成算法之一。线性同余发生器（LCG）以 $x_0$ 为随机种子，生成很多非负整数 $x_i$ ,它遵循以下规则： 给定非负整数 $a,b,c\space(0≤x_00,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)}

如果有解，第 $1$ 行输出 $s$，第 $2$ 行输出 $n$ 个 $t_j$ 。 $(0≤t_j≤10^9)$ 。 如果无解，输出 $-1$ 。

时间限制：1秒 空间限制：256MB