题目描述

Little Roman is studying linear congruential generators -- one of the oldest and best known pseudorandom number generator algorithms. Linear congruential generator (LCG) starts with a non-negative integer number $x_{0}$ also known as seed and produces an infinite sequence of non-negative integer numbers $x_{i} (0 \le x_{i} < c)$ which are given by the following recurrence relation:

$x_{i+1} = (ax_{i} + b)$ mod $c$

here a , $b$ , and $c$ are non-negative integer numbers and $0 \le x_{0} < c$ .

Roman is curious about relations between sequences generated by different LCGs. In particular, he has $n$ different LCGs with parameters $a^{(j)}, b^{(j)},$ and $c^{(j)}$ for $1 \le j \le n$ , where the j-th LCG is generating a sequence $x_{i}^{(j)}.$ He wants to pick one number from each of the sequences generated by each LCG so that the sum of the numbers is the maximum one, but is not divisible by the given integer number $k$ .

Formally, Roman wants to find integer numbers $t_{j} \ge 0$ for $1 \le j \le n$ to maximize $s = Σ^{n}_{j=1} x_{t_{j}}^{(j)}  subject$ to constraint that $s$ mod $k ≠ 0$ .

输入格式

The first line of the input file contains two integer numbers $n$ and $k (1 \le n \le 10 000 , 1 \le k \le 10^{9}).$ The following $n$ lines describe LCGs. Each line contains four integer numbers $x_{0}^{(j)}, a^{(j)}, b^{(j)},$ and $c^{(j)} (0 \le a^{(j)}, b^{(j)} \le 1000 , 0 \le x_{0}^{(j)} < c^{(j)} \le 1000)$ .

输出格式

If Roman's problem has a solution, then write on the first line of the output file a single integer $s$ -- the maximum sum not divisible by $k$ , followed on the next line by $n$ integer numbers $t_{j} (0 \le t_{j} \le 10^{9})$ specifying some solution with this sum.

Otherwise, write to the output file a single line with the number $−1$ .

题目大意

题目描述

罗曼在学习线性同余发生器——最古老，也是最广为人知的伪随机数生成算法之一。线性同余发生器（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$ 。

说明/提示

时间限制：1秒

空间限制：256MB

2 3
1 1 1 6
2 4 0 5

8
4 1

2 2
0 7 2 8
2 5 0 6

-1

提示

Time limit: 1 s, Memory limit: 256 MB.