생성기

선형 합동 생성기(LCG)는 음이 아닌 정수 $x_0$을 시드로 삼아 시작하고, $0 \le x_i < c$를 만족하는 정수 수열 $x_i$를 무한히 만든다.

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

$a$, $b$, $c$는 음이 아닌 정수이고 $0 \le x_0 < c$이다.

생성기 $n$개가 주어진다. $j$번 생성기의 매개변수는 $x_0^{(j)}$, $a^{(j)}$, $b^{(j)}$, $c^{(j)}$이고, 이 생성기는 수열 $x_i^{(j)}$를 만든다. 수열 $n$개에서 항을 하나씩 골라, 고른 항의 합을 최대로 하면서 그 합이 $k$의 배수가 되지 않게 하려고 한다.

식으로 쓰면 $1 \le j \le n$에 대해 정수 $t_j \ge 0$을 골라, $s \bmod k \neq 0$이라는 조건 아래에서 $s = \sum_{j=1}^{n} x_{t_j}^{(j)}$를 최대로 만드는 것이다.

첫째 줄에 정수 $n$과 $k$가 주어진다 ($1 \le n \le 10^4$, $1 \le k \le 10^9$).

다음 $n$개 줄에는 생성기 하나를 나타내는 정수 네 개 $x_0^{(j)}$, $a^{(j)}$, $b^{(j)}$, $c^{(j)}$가 주어진다 ($0 \le a^{(j)}, b^{(j)} \le 1000$, $0 \le x_0^{(j)} < c^{(j)} \le 1000$).

$k$의 배수가 아닌 합을 만들 수 없으면 첫째 줄에 -1을 출력한다.

만들 수 있으면 첫째 줄에 최대 합 $s$를 출력하고, 둘째 줄에 인덱스 $t_1, t_2, \dots, t_n$을 공백 하나로 구분해 출력한다 ($0 \le t_j \le 10^9$).

같은 최대 합을 만드는 인덱스 조합이 여러 가지일 수 있으므로, 다음 규칙이 정하는 조합을 그대로 출력한다. $j$번 수열에 나타나는 값 중 가장 큰 값을 $m_j$라 하고, $S = m_1 + m_2 + \dots + m_n$이라 하자.

• $S \bmod k \neq 0$이면 $s = S$이고, 모든 생성기가 자기 수열의 최댓값 $m_j$를 고른다.
• 그렇지 않으면 각 생성기 $j$에 대해, $j$번 수열에 나타나면서 $(m_j - v) \bmod k \neq 0$을 만족하는 값 $v$ 중 가장 큰 것을 $p_j$라 하고 $d_j = m_j - p_j$라 하자. 그런 $v$가 없는 생성기는 이 단계에서 제외한다. 그런 $v$가 있는 생성기가 하나도 없으면 -1을 출력한다. 있으면 $d_j$의 최솟값을 $D$, $d_j = D$인 가장 작은 번호를 $q$라 할 때 $s = S - D$이고, $q$번 생성기는 $p_q$를 고르며 나머지 생성기는 모두 자기 수열의 최댓값 $m_j$를 고른다.

각 생성기에 대해, 고른 값이 그 수열에서 처음 나타나는 인덱스 $t_j$를 출력한다.

첫 번째 예제에서 첫 생성기는 1, 2, 3, 4, 5, 0, 1, 2, ...를 만들고, 둘째 생성기는 2, 3, 2, 3, 2, ...를 만든다.

두 번째 예제에서 첫 생성기는 0, 2, 0, 2, 0, ...을 만들고, 둘째 생성기는 2, 4, 2, 4, 2, ...를 만든다.