Генератори#7567

Генератори

1 секунда

64 мегабайти

Складна

Маленький Роман вивчає лінійні конгруентні генератори — один з найстаріших і найвідоміших алгоритмів для генерації псевдовипадкових чисел. Лінійний конгруентний генератор (ЛКГ) починає свою роботу з невід'ємного цілого числа $x_{0}$ x_0, відомого як насіння, і генерує нескінченну послідовність невід'ємних цілих чисел $x_{i}$ x_i ( $0 \leq x_{i} < c$ 0 \le x_i < c), які визначаються за наступним рекурентним співвідношенням:

x_{i + 1} = (a \cdot x_{i} + b) mod c

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

де $a$ , $b$ і $c$ — невід'ємні цілі числа, і $0 \leq x_{0} < c$ 0 \le x_0 < c.

Роману цікаво дослідити взаємозв'язки між послідовностями, отриманими різними ЛКГ. У нього є $n$ різних ЛКГ з параметрами $a^{j}$ a^j, $b^{j}$ b^j і $c^{j}$ c^j для $1 \leq j \leq n$ 1 \le j \le n, де $j$ -ий ЛКГ генерує послідовність $x_{i}^{j}$ x^j_i. Він хоче вибрати одне число з кожної послідовності, згенерованої кожним ЛКГ, так, щоб їх сума була максимальною, але не ділилася на задане число $k$ . Формально, Роман прагне знайти такі цілі числа $t_{j} \geq 0$ t_j \ge 0 для $1 \leq j \leq n$ 1 \le j \le n, які максимізують

за умови, що $s mod k \neq = 0$ s \mod k \ne 0.

Вхідні дані

Перший рядок містить два цілі числа $n$ і $k$ ( $1 \leq n \leq 10000$ 1 \le n \le 10000, $1 \leq k \leq 1 0^{9}$ 1 \le k \le 10^9). Наступні $n$ рядків описують ЛКГ. Кожен рядок містить чотири числа $x_{0}^{j}$ x^j_0, $a^{j}$ a^j, $b^{j}$ b^j і $c^{j}$ c^j ( $0 \leq a^{j}, b^{j} \leq 1000$ 0 \le a^j, b^j \le 1000, $0 \leq x_{0}^{j} < c^{j} \leq 1000$ 0 \le x^j_0 < c^j \le 1000).

Вихідні дані

Якщо задача Романа має розв'язок, то в першому рядку виведіть число $s$ — значення найбільшої суми, що не ділиться на $k$ , а в другому рядку виведіть $n$ чисел $t_{j}$ t_j ( $0 \leq t_{j} \leq 1 0^{9}$ 0 \le t_j \le 10^9), які визначають деяке рішення для виведеної суми.

Якщо розв'язку не існує, виведіть $- 1$ в окремому рядку.

Приклади

Приклад 1

Приклад 2