Generators

A linear congruential generator (LCG) starts from a non-negative integer $x_0$, called the seed, and produces an infinite sequence of integers $x_i$ with $0 \le x_i < c$:

$x_{i+1} = (a \cdot x_i + b) \bmod c$

Here $a$, $b$ and $c$ are non-negative integers and $0 \le x_0 < c$.

You are given $n$ generators. The parameters of generator $j$ are $x_0^{(j)}$, $a^{(j)}$, $b^{(j)}$ and $c^{(j)}$, and it produces the sequence $x_i^{(j)}$. Take one term from each of the $n$ sequences so that the sum of the taken terms is as large as possible and is not divisible by $k$.

Formally, choose integers $t_j \ge 0$ for $1 \le j \le n$ that maximize $s = \sum_{j=1}^{n} x_{t_j}^{(j)}$ subject to $s \bmod k \neq 0$.

The first line contains two integers $n$ and $k$ ($1 \le n \le 10^4$, $1 \le k \le 10^9$).

Each of the next $n$ lines describes one generator with four integers $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 no choice of terms gives a sum that is not divisible by $k$, print a single line containing -1.

Otherwise print the maximum sum $s$ on the first line, and on the second line the $n$ indices $t_1, t_2, \dots, t_n$ separated by single spaces ($0 \le t_j \le 10^9$).

Several sets of indices can reach the same maximum sum, so print exactly the one this rule produces. Let $m_j$ be the largest value that occurs in sequence $j$, and let $S = m_1 + m_2 + \dots + m_n$.

• If $S \bmod k \neq 0$, then $s = S$ and every generator takes the largest value $m_j$ of its own sequence.
• Otherwise, for each generator $j$ let $p_j$ be the largest value $v$ occurring in sequence $j$ with $(m_j - v) \bmod k \neq 0$, and let $d_j = m_j - p_j$. A generator with no such $v$ is left out of this step. If no generator has such a $v$, print -1. Otherwise let $D$ be the smallest $d_j$ and let $q$ be the smallest index $j$ with $d_j = D$. Then $s = S - D$, generator $q$ takes the value $p_q$, and every other generator takes the largest value $m_j$ of its own sequence.

For each generator, print the smallest index $t_j$ at which the value it takes occurs in its sequence.

In the first example the first generator produces 1, 2, 3, 4, 5, 0, 1, 2, ... and the second generator produces 2, 3, 2, 3, 2, ....

In the second example the first generator produces 0, 2, 0, 2, 0, ... and the second generator produces 2, 4, 2, 4, 2, ....