Generatorlar

Kiçik Roman xətti kongruent generatorları öyrənir - təsadüfi ədədlərin yaradılması üçün ən qədim və məşhur alqoritmlərdən biridir. Xətti kongruent generator (XKG) toxum adlanan toxunulmamış tam ədəd x[0] ilə başlayır və aşağıdakı rekursiv əlaqə ilə müəyyən edilən sonsuz toxunulmamış tam ədədlər ardıcıllığını x[i] (0 ≤ x[i] < c) istehsal edir:

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

burada a, b və c toxunulmamış tam ədədlərdir və 0 ≤ x[0] < c.

Roman müxtəlif XKG-lər tərəfindən yaradılan ardıcıllıqlar arasındakı əlaqələri araşdırır. Onun n müxtəlif XKG-si var, parametrləri a^j, b^j və c^j olan, burada 1 ≤ j ≤ n, j-ci XKG x^j[i] ardıcıllığını yaradır. O, hər bir XKG tərəfindən yaradılan ardıcıllıqdan bir ədəd seçmək istəyir ki, onların cəmi ən böyük olsun, lakin verilmiş k ədədinə bölünməsin. Formal olaraq, Roman belə tam ədədləri t[j] ≥ 0 üçün 1 ≤ j ≤ n tapmaq istəyir ki, onlar

şərti ilə s mod k ≠ 0 maksimumlaşdırır.

Giriş məlumatları

Birinci sətir iki tam ədəd n və k (1 ≤ n ≤ 10 000, 1 ≤ k ≤ 10^9) ehtiva edir. Növbəti n sətir XKG-ləri xarakterizə edir. Hər bir sətir dörd ədəd x^j[0], a^j, b^j və c^j (0 ≤ a^j, b^j ≤ 1000, 0 ≤ x^j[0] < c^j ≤ 1000) ehtiva edir.

Çıxış məlumatları

Əgər Romanın problemi həll olunarsa, birinci sətirdə s ədədini - k-ya bölünməyən ən böyük cəmin qiymətini, ikinci sətirdə isə n ədədini t[j] (0 ≤ t[j] ≤ 10^9) çıxış edin, bu cəmin bəzi həllini təyin edir.

Əks halda, ayrıca bir sətirdə -1 çıxış edin.