Sub2max

Gigel participă la olimpiada de informatică și se confruntă cu următoarea provocare: el dispune de un șir de $N$ numere și dorește să găsească o subsecvență cu lungimea cuprinsă între $S$ și $D$, astfel încât suma elementelor din această subsecvență să fie maximă. Mai mult, Gigel a decis că această sumă trebuie să fie și o putere a lui $K$.
Scopul este de a scrie un program care să determine subsecvența cu lungimea între $S$ și $D$ care are suma elementelor cea mai mare și este putere a lui $K$.
Dacă mai multe subsecvențe au aceeași sumă maximă, dar nu au aceeași lungime, se va afișa indicele de început al celei mai scurte subsecvențe. Dacă mai multe subsecvențe au aceeași sumă maximă și aceeași lungime minimă, se va afișa indicele de început al ultimei subsecvențe găsite.

Date de intrare

Fișierul de intrare sub2max.in conține pe prima linie patru numere întregi, $N, S, D$ și $K$, separate prin spațiu. Pe următoarea linie se vor afla $N$ numere, elementele șirului.

Date de ieșire

Fișierul de ieșire sub2max.out va conține pe prima linie două numere: suma maximă care este putere a lui $K$ și indicele de început al subsecvenței corespunzătoare acestei sume.

Restricții și precizări

• $1 \leq N \leq 10^4$
• $1 \leq S \leq D \leq N$
• $1 \leq K \leq 130$
• Elementele șirului sunt numere în intervalul $[−10^7, 10^7]$
• În cazul în care nu există soluție se va afișa $-1$ atât pentru valoarea sumei maxime, cât și pentru indicele de început.
• Indicii șirului se numerotează începând de la $1$.
• Pentru teste in valoare de $30$ de puncte $N \leq 10^3$
• Pentru alte teste în valoare de $70$ de puncte, nu există restricții suplimentare.

Exemplul 1

sub2max.in

5 1 3 3
3 12 15 12 15

sub2max.out

27 4

Explicație

Avem un șir de $5$ numere și trebuie să găsim o subsecvență cu lungimea între $1$ și $3$ elemente, astfel încât suma elementelor să fie maximă și să fie o putere a lui $3$. Cea mai mare sumă care este o putere a lui $3$ și care respectă condițiile de lungime a subsecvenței este $27$, iar aceasta este obținută pentru subsecvențele de lungime $2$ care încep de la indicele $2, 3$ și respectiv $4$. Cum în acest caz toate cele trei subsecvențe au aceeași lungime minimă $2$, se va lua în considerare indicele de început al ultimei subsecvențe găsite, anume $4$.

Exemplul 2

sub2max.in

7 2 4 2
1 2 4 8 16 32 64

sub2max.out

-1 -1

Explicație

Avem un șir de $7$ numere și trebuie să găsim o subsecvență cu lungimea între $2$ și $4$ elemente, astfel încât suma elementelor să fie maximă și să fie o putere a lui $2$. În șirul dat nu există nicio subsecvență astfel încât suma elementelor să fie maximă și să fie o putere a lui $2$.

Exemplul 3

sub2max.in

10 2 5 2
-1 3 -2 7 4 1 6 3 2 -5

sub2max.out

16 5

Explicație

Avem un șir de $10$ numere și trebuie să găsim o subsecvență cu lungimea între $2$ și $5$ elemente, astfel încât suma elementelor să fie maximă și să fie o putere a lui $2$. Cea mai mare sumă care este o putere a lui $2$ și care respectă condițiile de lungime a subsecvenței este $16$, iar aceasta este obținută pentru subsecvența care începe de la indicele $3$ si are lungimea $16 \ ([-2, 7, 4, 1, 6])$ și pentru subsecvența care începe de la indicele $5$ și are lungimea $16 \ ([4, 1, 6, 3, 2])$. Cum în acest caz ambele subsecvențe au aceeași lungime minimă $2$, se va lua în considerare indicele de început al ultimei subsecvențe găsite, anume $5$.