mario

Mario și Wario participă la o cursă alergând unul lângă celălalt. Amândoi sar deodată peste exact același număr de obstacole.

• Înălțimile săriturilor lui Mario sunt date ca un șir de $N$ numere naturale.
• Înălțimile săriturilor lui Wario sunt date ca un alt șir de $N$ numere naturale.

De fiecare dată când sar, ei consumă energie. Energia unei singure sărituri este egală cu înălțimea săriturii. De exemplu, o săritură de înălțime $5$ consumă energie $5$.

Rivalitatea dintre cei doi este legendară și extrem de echilibrată. Statisticile competiției arată că pentru orice obstacol din cursă, diferența (în valoare absolută) dintre suma energiilor consumate de Mario și suma energiilor consumate de Wario de la începutul cursei până la acel obstacol nu depășește niciodată valoarea de $450 \ 000$.

Cerință

Se dau $C$, reprezentând cerința care trebuie rezolvată ($C = 1$, $C = 2$ sau $C = 3$), $N$, numărul de sărituri, $K$ și cele două șiruri de $N$ valori naturale, cu semnificația din enunț.

• Dacă $C = 1$, găsiți indicele minim al săriturii la care diferența, în valoare absolută, dintre energia consumată de Mario și energia consumată de Wario a fost cea mai mare;
• Dacă $C = 2$, Mario vrea să analizeze efortul depus pe porțiuni de lungime fixă $K$. Găsiți secvența de lungime exact $K$ unde Mario a consumat în total cea mai multă energie și aflați indicele de început al acestei secvențe. Dacă există mai multe secvențe cu aceeași energie maximă, se afișează cea cu indicele minim;
• Dacă $C = 3$, găsiți un segment al cursei (o secvență compusă din una sau mai multe sărituri consecutive) unde Mario și Wario au consumat exact aceeași energie totală, chiar dacă săriturile lor individuale au fost diferite și aflați indicii $st$ și $dr$ între care este cuprins acest segment. Dacă există mai multe astfel de segmente, se afișează cel cu $st$ minim. Dacă există mai multe segmente cu $st$ minim, se afișează cel cu $dr$ minim.

Date de intrare

Pe prima linie a fișierului mario.in se află numerele $C$, $N$ și $K$.
Pe a doua linie se află $N$ numere naturale reprezentând înălțimile săriturilor lui Mario.
Pe a treia linie se află $N$ numere naturale reprezentând înălțimile săriturilor lui Wario.
Numerele de pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

În fișierul de ieșire mario.out se află:

• Un singur număr reprezentând indicele săriturii cu diferența maximă, dacă $C = 1$;
• Un singur număr reprezentând indicele de început al secvenței de lungime $K$ cu suma maximă pentru Mario, dacă $C = 2$;
• Două numere întregi $st$ și $dr$, reprezentând indicii de început și de sfârșit ai unui segment conform cerinței, dacă $C = 3$. Dacă nu există un astfel de segment, se afișează -1 -1.

Restricții și precizări

• $1 \le N \le 10^6$;
• $1 \le K \le N$;
• Toate înălțimile săriturilor au valori între $1$ și $10^4$;
• Numerotarea săriturilor se face începând de la indicele $1$.

Exemplul 1

mario.in

1 4 1
3 4 5 2
1 5 4 3

mario.out

1

Explicație

Diferențele absolute la fiecare săritură sunt:

• Indice $1$: $|3 - 1| = 2$;
• Indice $2$: $|4 - 5| = 1$;
• Indice $3$: $|5 - 4| = 1$;
• Indice $4$: $|2 - 3| = 1$.

Maximul este $2$, obținut la indicele $1$.

Exemplul 2

mario.in

2 5 2
2 5 1 6 3
1 1 1 1 1

mario.out

4

Explicație

Sumele din secvențele de lungime exact $2$ sunt:

• Indice $1$: $(2, 5)$, $2 + 5 = 7$;
• Indice $2$: $(5, 1)$, $5 + 1 = 6$;
• Indice $3$: $(1, 6)$, $1 + 6 = 7$;
• Indice $4$: $(6, 3)$, $6 + 3 = 9$.

Maximul de energie consumată de Mario este $9$, iar secvența de sărituri începe cu indicele $4$.

Exemplul 3

mario.in

3 4 1
3 4 5 2
1 5 4 3

mario.out

2 3

Explicație

Un segment al cursei unde Mario și Wario au consumat aceeași energie totală este de la $2$ la $3$:

• Mario $[4, 5]$: energie $4 + 5 = 9$;
• Wario $[5, 4]$: energie $5 + 4 = 9$.

Energiile sunt egale pe segmentul $2\ 3$, prin urmare $st = 2$ și $dr = 3$.

Exemplul 4

mario.in

3 3 1
1 1 1
2 2 2

mario.out

-1 -1

Explicație

Săriturile lui Wario sunt întotdeauna mai mari. Energia sa totală va fi întotdeauna mai mare decât a lui Mario pe orice segment. Nu există nicio potrivire, prin urmare $st = -1$ și $dr = -1$.