Generators#7567
Little Roman is studying linear congruential generators - one of the oldest and best known pseudo-random 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:
here , and 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 different LCGs with parameters a^j, b^j and c^j for 1 \le j \le n, where the -th LCG is generating a sequence x^j_i. 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 . Formally, Roman wants to find integer numbers t_j \ge 0 for 1 \le j \le n to maximize
subject to constraint that s \bmod k \ne 0.
The first line contains two integer numbers and (1 \le n \le 10000, 1 \le k \le 10^9). The following lines describe LCGs. Each line contains four integer numbers x^j_0, a^j, b^j and c^j (0 \le a^j, b^j \le 1000, 0 \le x^j_0 < c^j \le 1000).
If Roman's problem has a solution, then write on the first line a single integer - the maximum sum not divisible by , followed on the next line by integer numbers t_j (0 \le t_j \le 10^9) specifying some solution with this sum.
Otherwise, write to the output a single line with the number .
Пример 1
Пример 2