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

Se dau C, reprezentând cerința care trebuie rezolvată (C = 1, C = 2 sau C = 3), N, numărul de sărituri, 𝐾 ș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 afișaț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 afișaț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ă nu există un astfel de segment, se afișează -1 -1, dacă C = 3.

Restricții și precizări

• 1 ≤ N ≤ 1.000.000
• 1 ≤ K ≤ N
• Toate înălțimile săriturilor au valori între 1 și 10.000.
• Numerotarea săriturilor se face începând de la indicele 1.
• Datorită dimensiunilor mari, nu au fost adăugate toate testele folosite în concurs.

Exemplul 1

mario.in

1 4 1
3 4 5 2
1 5 4 3

mario.out

1

Explicație

Diferent, 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 2 3.

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

Energiile sunt egale pe segmentul de cursă 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.