Se dau N puncte în spațiul 3D prin coordonatele lor. Dorim să amplasăm două cuburi cu laturile paralele cu axele de coordonate, astfel încât fiecare punct să se afle pe una dintre feţele sau în interiorul a cel puțin unuia dintre cuburi. În plus, latura cubului de latură maximă dintre cele două trebuie să fie minimă.

Cerința

Scrieţi un program care să determine latura cubului de latură maximă pentru două cuburi care realizează acoperirea mulțimii de puncte în condiţiile de mai sus.

Date de intrare

Pe prima linie a fişierului cuburi.in se află 10 numere naturale N, Ax, Bx, Cx, Ay, By, Cy, Az, Bz, Cz. Coordonatele celor N puncte se generează după următoarele reguli:

• X1 = 1, Xi = (Xi-1 * Ax + Bx * i) mod Cx, pentru i = 2...n
• Y1 = 1, Yi = (Yi-1 * Ay + By * i) mod Cy, pentru i = 2...n
• Z1 = 1, Zi = (Zi-1 * Az + Bz * i) mod Cz, pentru i = 2...n

Al i-lea punct are coordonatele (Xi, Yi, Zi).

Date de ieșire

Fişierul de ieşire cuburi.out va conţine un singur număr natural reprezentând latura cubului de latură maximă.

Restricții și precizări

• 1 ≤ N ≤ 2*1.000.000
• 1 ≤ Ax, Ay, Az ≤ 1000
• 1 ≤ Bx, By, Bz ≤ 1010
• 2 ≤ Cx, Cy, Cz ≤ 1015
• Un punct aflat pe o față a cubului (inclusiv pe o muchie sau într-un colț al cubului) se consideră în interiorul cubului
• Pentru teste în valoare de 30 de puncte N ≤ 100 și Cx, Cy, Cz ≤ 20
• Pentru teste în valoare de 60 de puncte N ≤ 10.000

Exemplu:

cuburi.in

6 2 3 10 3 1 9 5 7 8

cuburi.out

5

Explicație

Cele 6 puncte au următoarele coordonate: (1,1,1), (8,5,3), (5,0,4), (2,4,0), (9,8,3), (6,3,1). O soluție posibilă este să amplasăm primul cub astfel încât două dintre colțurile opuse să aibă coordonatele (0, 0, 0) respectiv (5,5,5) iar al doilea cub să aibă două colțuri opuse la coordonatele (6,3,1), respectiv (11,8,6).