eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Генераторы

Генераторы

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Маленький Роман изучает линейные конгруэнтные генераторы - один из старейших и наиболее известных алгоритмов генерации псевдослучайных чисел. Линейный конгруэнтный генератор (ЛКГ) начинает свою работу с неотрицательного целого числа x[0] известного как семя и производит бесконечную последовательность неотрицательных целых чисел x[i] (0x[i] < c), которые задаются следующим рекуррентным соотношением:

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

здесь a, b и c - неотрицательные целые и 0x[0] < c.

Роману любопытны соотношения между последовательностями, полученными разными ЛКГ. У него имеется n различных ЛКГ с параметрами a^j, b^j и c^j для 1jn, где j-ый ЛКГ генерирует последовательность x^j[i]. Он хочет выбрать одно число из каждой последовательности сгенерированной каждой ЛКГ так чтобы их сумма была наибольшей, но не делится на заданное число k. Формально, Роман хочет найти такие целые числа t[j]0 для 1jn, которые максимизируют

prb7567.gif

при условии что s mod k0.

Вхідні дані

Первая строка содержит два целых числа n и k (1n10 000, 1k10^9). Следующие n строк характеризуют ЛКГ. Каждая строка содержит четыре числа x^j[0] , a^j, b^j и c^j (0a^j, b^j1000, 0x^j[0] < c^j1000).

Вихідні дані

Если задача Романа имеет решение, то в первой строке вывести число s - значение наибольшей суммы, не делящейся на k, а во второй строке вывести n чисел t[j] (0t[j]10^9) задающих некоторое решение для выведенной суммы.

Иначе в отдельной строке выведите -1.

Приклад

Вхідні дані #1
2 3
1 1 1 6
2 4 0 5
Вихідні дані #1
8
4 1
Вхідні дані #2
2 2
0 7 2 8
2 5 0 6
Вихідні дані #2
-1
Джерело 2015 ACM NEERC, Semifinals, December 6, Problem G