SPOJ in Armenian

Տրված են ոչ բացասական ամբողջ թվերի n հավաքածուներ։ Խաղացողը սկսում է առաջին հավաքածուից և ամեն հերթական հավաքածուից ընտրում մեկ թիվ՝ այն պայմանով, որ ընտրված յուրաքանչյուր թիվ պետք է փոքր չլինի նախորդ ընտրածից։ Այլ կերպ ասած, խաղացողը i-րդ քայլին մեկ թիվ է ընտրում i-րդ հավաքածուից, և եթե նա i-րդ քայլին ընտրել է x թիվը, իսկ i+1 քայլին՝ y-ը, ապա x ≤ y: Խաղացողը հաղթում է, եթե կարողանում է վերջին հավաքածուից ընտրել թիվ և ստանում է վերջին ընտրած թվին հավասար միավոր։ Օգնեք խաղացողին մաքսիմիզացնել արդյունքը։

Որպես պատասխան պետք է արտածել առավելագույն միավորը, որը կարող է ստանալ խաղացողը։ Եթե խաղացողը չի կարող հաղթել, պետք է արտածել '-1':

Մուտքային տվյալներ

Առաջին տողում տրված է հավաքածուների n (1 ≤ n ≤ 10⁵) քանակը։ Հաջորդ n տողերից i-րդում տրված են m[i], a[i], b[i], q[i] և t[i] թվերը։ i-րդ հավաքածուին (x[i] հավաքածուին) պատկանող թվերը որոշվում են հետևյալ կերպ.

x[i][1] = t[i],

x[i][j] = (a[i] * x[i][j - 1] + b[i]) % q[i], եթե 2 ≤ j ≤ m[i]:

Երաշխավորվում է, որ m[i] ≥ 1,

1 ≤ a[i], b[i] < q[i] ≤ 10⁹,

0 ≤ t[i] ≤ 10⁹:

Ելքային տվյալներ

Անհրաժեշտ է արտածել մեկ թիվ՝ առավելագույն միավորը, որը կարող է ստանալ խաղացողը խաղի վերջում։ Եթե հաղացողը չի կարող հաղթել, անհրաժեշտ է արտածել '-1':

Օրինակներ

Բացատրություն

Երկրորդ օրինակում առաջին հավաքածուն կլինի՝

x[1][1] = 2,

x[1][2] = (4 * x[1][1] + 8) % 11 = 5,

x[1][3] = (4 * x[1][2] + 8) % 11 = 6,

x[1][4] = (4 * x[1][3] + 8) % 11 = 10,

x[1][5] = (4 * x[1][4] + 8) % 11 = 4,

x[1][6] = (4 * x[1][5] + 8) % 11 = 2,

x[1][7] = (4 * x[1][6] + 8) % 11 = 5:

Երկրորդ հավաքածուն կլինի՝

x[2][1] = 7,

x[2][2] = (1 * x[2][1] + 7) % 8 = 6,

x[2][3] = (1 * x[2][2] + 7) % 8 = 5:

Իսկ երրորդ հավաքածուն ունի մեկ տարր՝ 999999999: Խաղացողը հավաքածուներից կարող է ընտրել համապատասխանաբար 6, 7, 999999999 թվերը, և արդյունքում կստանա 999999999 միավոր։