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

xi+1 = (a *xi + b) mod c

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

Роману любопытны соотношения между последовательностями, полученными разными ЛКГ. У него имеется n различных ЛКГ с параметрами aj, bj и cj для 1 ≤ j ≤ n, где j-ый ЛКГ генерирует последовательность xj[i]. Он хочет выбрать одно число из каждой последовательности сгенерированной каждой ЛКГ так чтобы их сумма была наибольшей, но не делится на заданное число k. Формально, Роман хочет найти такие целые числа tj ≥ 0 для 1 ≤ j ≤ n, которые максимизируют

при условии что s mod k ≠ 0.

Входные данные

Первая строка содержит два целых числа n и k (1 ≤ n ≤ 10 000, 1 ≤ k ≤ 109). Следующие n строк характеризуют ЛКГ. Каждая строка содержит четыре числа xj[0] , aj, bj и cj (0 ≤ aj, bj ≤ 1000, 0 ≤ xj[0] < cj ≤ 1000).

Выходные данные

Если задача Романа имеет решение, то в первой строке вывести число s - значение наибольшей суммы, не делящейся на k, а во второй строке вывести n чисел tj (0 ≤ tj ≤ 109) задающих некоторое решение для выведенной суммы.

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