cuburi

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ță

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$, $A_x$, $B_x$, $C_x$, $A_y$, $B_y$, $C_y$, $A_z$, $B_z$, $C_z$. Coordonatele celor $N$ puncte se generează după următoarele reguli:

• $X_1 = 1, X_i = (X_{i-1} \cdot A_x + B_x \cdot i)$ mod $C_x$, pentru $i = 2 \dots n$
• $Y_1 = 1, Y_i = (Y_{i-1} \cdot A_y + B_y \cdot i)$ mod $C_y$, pentru $i = 2 \dots n$
• $Z_1 = 1, Z_i = (Z_{i-1} \cdot A_z + B_z \cdot i)$ mod $C_z$, pentru $i = 2 \dots n$

Al $i$-lea punct are coordonatele $(X_i, Y_i, Z_i)$.

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 \leq N \leq 2 \cdot 10^{6}$
• $1 \leq A_x, A_y, A_z \leq 1 \ 000$
• $1 \leq B_x, B_y, B_z \leq 10^{10}$
• $2 \leq C_x, C_y, C_z \leq 10^{15}$
• Un punct aflat pe o față a cubului (inclusiv pe o muchie sau într-un colț al cubului) se consideră în interiorul cubului
• Pentru un număr de teste în valoare de $30$ de puncte $N \leq 100$ și $C_x, C_y, C_z \leq 20$
• Pentru un număr de teste în valoare de $70$ de puncte $N \leq 10^{5}$

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)$.