Bobby

În timpul orei de geografie, amicul nostru Bobby primește o problemă năstrușnică de la colegul său, Fischer. Aflându-se într-o lipsă totală de idei și nevrând să-l dezamăgească pe Fischer, vă cere ajutorul. Năstrușnica problemă a lui Fischer este următoarea.

Cerință

Dându-se un șir de valori, reprezentând costurile a $M$ muchii bidirecționale, construiți un graf conex, având doar aceste muchii, astfel încât costul arborelui parțial de cost minim al său să fie maxim.

Date de intrare

Pe prima linie a fișierului de intrare bobby.in se găsesc două numere întregi, $N$ și $M$, reprezentând numărul de noduri, respectiv numărul de muchii pe care trebuie să le aibă graful construit. Pe a doua linie se găsesc șase numere întregi, $X$, $Y$, $A$, $B$, $C$ și $D$, care vor genera șirul de $M$ valori, notat cu $V$, după următoarele reguli:

• $\displaystyle V_1 = X$;
• $\displaystyle V_2 = Y$;
• $\displaystyle V_i = (A \cdot V_{i-2} + B \cdot V_{i-1} + C)\text{ mod }D$, oricare ar fi $i$ cu $3 \leq i \leq M$.

Date de ieșire

Pe prima linie a fișierului de ieșire bobby.out se va găsi un singur număr întreg, costul arborelui parțial de cost minim al grafului construit sau $-1$, în cazul în care nu se poate construi un graf care să respecte cerința.

Restricții și precizări

• $2 \leq N, M \leq 1 \ 000 \ 000$;
• $0 \leq X, Y, A, B, C, D \leq 1 \ 000 \ 000 \ 000$, $D \neq 0$;
• Între oricare două noduri din graful construit trebuie să existe cel mult o muchie.

Exemplu

bobby.in

4 5
1 1 1 1 1 3

bobby.out

1

Explicație

Șirul de $M$ muchii este: $1 \ 1 \ 0 \ 2 \ 0$.
Construim graful astfel:

• Între nodurile $1$ și $2$, muchie de cost $2$.
• Între nodurile $1$ și $3$, muchie de cost $0$.
• Între nodurile $1$ și $4$, muchie de cost $0$.
• Între nodurile $2$ și $3$, muchie de cost $1$.
• Între nodurile $3$ și $4$, muchie de cost $1$.