Problem 4048: 1337

Cerință

Gigel, mare hacker de meserie, vrea să afle secretul spus de Marius Mariei. Gigel interceptează mesajul, vede că este format din $n$ numere întregi, însă își dă seama că este criptat. Pentru a decripta mesajul, acesta are nevoie de numărul special $X$ din mesaj. $X$ este elementul maxim care se află într-o subsecvență a cărei sumă mod $k$ este egală cu $p$ .
Ajutați-l pe Gigel să decripteze mesajul, pentru a afla secretul. Dacă mai multe subsecvențe conțin elementul maxim $X$ , alegeți subsecvența specială (cea mai scurtă). Dacă există mai multe subsecvențe de lungime minimă, alegeți subsecvența cu indicele $j$ cel mai mic. Dacă nu există o subsecvență a cărei sumă mod $k$ este egală cu $p$ , afișați mesajul „Nu exista”. Numim subsecvență orice alăturare de elemente consecutive (în vector): $v_i, v_{i+1}, v_{i+2}, \ldots, v_j$ .

Date de intrare

Pe prima linie a fișierului de intrare 1337.in se găsesc trei numere întregi, $n$ , $k$ și $p$ (numărul de elemente din vector, respectiv $k$ și $p$ , cu specificația de mai sus).
Pe a doua linie, se găsesc $n$ numere întregi, separate prin spațiu (elementele vectorului).

Date de ieșire

Pe prima linie a fișierului de ieșire 1337.out se va găsi un singur număr întreg $X$ .
Pe a doua linie, se vor găsi două numere întregi, separate prin spațiu, reprezentând indicii care delimitează subsecvența.

Restricții și precizări

$1 \le n \le 100\,000$
$-10^{18} \le v[i] \le 10^{18}$
$0 \le p < k \le 10^{18}$
Pentru 20 de puncte, $1 \le n \le 2500$
Pentru alte 30 de puncte, $1 \le n \le 50 000$
Pentru afișarea corectă a numărului special $X$ , se acordă 40% din punctajul pe subtask.

Exemplul 1

1337.in

6 5 0
3 1 4 2 5 1

1337.out

5
5 5

Explicație

Subsecvențele cu suma mod $5$ egală cu $0$ sunt:

$3, 1, 4, 2$ — sumă $10 \rightarrow 10 \bmod 5 = 0$ (element maxim = 4)

$3, 1, 4, 2, 5$ — sumă $15 \rightarrow 15 \bmod 5 = 0$ (element maxim = 5, lungime = 5)

$1, 4$ — sumă $5 \rightarrow 5 \bmod 5 = 0$ (element maxim = 4)

$5$ — sumă $5 \rightarrow 5 \bmod 5 = 0$ (element maxim = 5, lungime = 1)

Numărul special $X = 5$ , iar indicii care delimitează subsecvența specială sunt 5 și 5.

Exemplul 2