Генератори
Маленький Роман вивчає лінійні конгруентні генератори — один з найстаріших і найвідоміших алгоритмів для генерації псевдовипадкових чисел. Лінійний конгруентний генератор (ЛКГ) починає свою роботу з невід'ємного цілого числа x[0], відомого як насіння, і генерує нескінченну послідовність невід'ємних цілих чисел x[i] (0 ≤ x[i] < c), які визначаються за наступним рекурентним співвідношенням:
x[i+1] = (a * x[i] + b) mod c
де a, b і c — невід'ємні цілі числа, і 0 ≤ x[0] < c.
Роману цікаво дослідити взаємозв'язки між послідовностями, отриманими різними ЛКГ. У нього є n різних ЛКГ з параметрами a^j, b^j і c^j для 1 ≤ j ≤ n, де j-ий ЛКГ генерує послідовність x^j[i]. Він хоче вибрати одне число з кожної послідовності, згенерованої кожним ЛКГ, так, щоб їх сума була максимальною, але не ділилася на задане число k. Формально, Роман прагне знайти такі цілі числа t[j] ≥ 0 для 1 ≤ j ≤ n, які максимізують
за умови, що s mod k ≠ 0.
Вхідні дані
Перший рядок містить два цілі числа n і k (1 ≤ n ≤ 10 000, 1 ≤ k ≤ 10^9). Наступні n рядків описують ЛКГ. Кожен рядок містить чотири числа x^j[0], a^j, b^j і c^j (0 ≤ a^j, b^j ≤ 1000, 0 ≤ x^j[0] < c^j ≤ 1000).
Вихідні дані
Якщо задача Романа має розв'язок, то в першому рядку виведіть число s — значення найбільшої суми, що не ділиться на k, а в другому рядку виведіть n чисел t[j] (0 ≤ t[j] ≤ 10^9), які визначають деяке рішення для виведеної суми.
Якщо розв'язку не існує, виведіть -1 в окремому рядку.