eolymp
bolt
Try our new interface for solving problems
Problems

Generators

Generators

Time limit 1 second
Memory limit 64 MiB

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-negativeinteger number x[0] also known as seed and produces an infinite sequence of non-negative integer numbers x[i] (0x[i] < c) which are given by the following recurrence relation:

x[i+1] = (a *x[i] + b) mod c

here a, b and c are non-negative integer numbers and 0x[0] < c.

Roman is curious about relations between sequences generated by different LCGs. In particular, he hasn different LCGs with parameters a^j, b^j and c^j for 1jn, where the j-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 k. Formally, Roman wants to find integer numbers t[j]0 for 1jn to maximize

prb7567.gif

subject to constraint that s mod k0.

Input data

The first line contains two integer numbers n and k (1n10 000, 1k10^9). The following n lines describe LCGs. Each line contains four integer numbers x^j[0] , a^j, b^j and c^j (0a^j, b^j1000, 0x^j[0] < c^j1000).

Output data

If Roman’s problem has a solution, then write on the first line a single integer s - the maximum sum not divisible by k, followed on the next line by n integer numbers t[j] (0t[j]10^9) specifying some solution with this sum.

Otherwise, write to the output a single line with the number -1.

Examples

Input example #1
2 3
1 1 1 6
2 4 0 5
Output example #1
8
4 1
Input example #2
2 2
0 7 2 8
2 5 0 6
Output example #2
-1
Source 2015 ACM NEERC, Semifinals, December 6, Problem G