Генераторы
Маленький Роман изучает линейные конгруэнтные генераторы - один из старейших и наиболее известных алгоритмов генерации псевдослучайных чисел. Линейный конгруэнтный генератор (ЛКГ) начинает свою работу с неотрицательного целого числа 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.