Fie un șir a = a1, a2, …, aN de numere naturale, nu neapărat distincte, cuprinse între 1 și N. Fie de asemenea două numere naturale x și y. Se definește operația transform(i) astfel: se determină valoarea w = 1 + (x * i + y * ai) mod N, apoi toate elementele egale cu ai din secvența ai, ai+1, …, aN își modifică valoarea în w. De exemplu, pentru șirul a=1, 7, 1, 7, 3, 4, 7, x = 4, y = 5, operația transform(4) înseamnă că w = 1+(4*4+5*7) mod 7 = 3, deci șirul devine 1, 7, 1, 3, 3, 4, 3 (toate elementele de la poziția 4 la 7 și egale cu 7 s-au modificat în 3). După fiecare operație de tip transform se calculează suma elementelor șirului obținut.

Cerința

Să se determine suma maximă care s-a obținut în șirul a efectuând pe rând asupra șirului operațiile transform(1), transform(2), …, transform(N).

Date de intrare

Fișierul de intrare transform.in conține pe prima linie numerele naturale N, x și y. Pe linia a doua se găsesc, separate prin spațiu, elementele șirului a.

Date de ieșire

Fișierul de ieșire transform.out va conține pe prima linie un singur număr natural reprezentând suma maximă obținută.

Restricții și precizări

• 3 ≤ N ≤ 256.000
• 1 ≤ x, y ≤ N

Exemplu:

transform.in

7 4 5
1 7 1 7 3 4 7

transform.out

35

Explicație

După transform(1), în care w = 3, șirul devine 3, 7, 3, 7, 3, 4, 7 care are suma 34.
După transform(2), în care w = 2, șirul devine 3, 2, 3, 2, 3, 4, 2 care are suma 19.
După transform(3), în care w = 7, șirul devine 3, 2, 7, 2, 7, 4, 2 care are suma 27.
După transform(4), în care w = 6, șirul devine 3, 2, 7, 6, 7, 4, 6 care are suma 35.
După transform(5), în care w = 7, șirul devine 3, 2, 7, 6, 7, 4, 6 care are suma 35.
După transform(6), în care w = 3, șirul devine 3, 2, 7, 6, 7, 3, 6 care are suma 34.
După transform(7), în care w = 3, șirul devine 3, 2, 7, 6, 7, 3, 3 care are suma 31.
Suma maximă care s-a obținut este 35.