kpower

Un număr natural se numește kpower dacă este putere a numărului natural $k$. O secvență kpower este un subşir de numere kpower care apar pe poziţii consecutive într-un şir.

Cerinţă

Fiind dat un un număr natural $k$ și un şir de $n$ numere naturale, scrieți un program care rezolvă următoarele cerințe:

1. Determină cel mai mare număr kpower dintre cele $n$ numere date.
2. Determină lungimea maximă a unei secvențe kpower.
3. Determină cea mai mare sumă ce se poate obține adunând numerele dintr-o secvență kpower de lungime maximă.

Date de intrare

Fişierul de intrare kpower.in conţine pe prima linie numărul $C$ reprezentând cerința ($1$, $2$ sau $3$), pe a doua linie numerele $k$ și $n$, iar pe a treia linie un șir de $n$ numere, numerele de pe aceeași linie fiind separate prin câte un spațiu.

Date de ieşire

Dacă cerința $C=1$, atunci pe prima linie a fişierului de ieşire kpower.out se va scrie cel mai mare număr kpower găsit.
Dacă cerința $C=2$, atunci pe prima linie a fişierului de ieşire kpower.out se va scrie lungimea maximă a unei secvențe kpower.
Dacă cerința $C=3$, atunci pe prima linie a fişierului de ieşire kpower.out se va scrie suma maximă a unei secvențe kpower de lungime maximă.

Restricţii şi precizări

• $0 < k \leq 9$
• $1 \leq n \leq 10^{6}$
• Cele $n$ numere citite sunt din intervalul $[0,10^{12}]$.
• Pentru toate datele de test, există cel puțin un număr kpower printre cele $n$ numere.
• Pentru teste valorând $20$ de puncte, $C=1$.
• Pentru teste valorând $30$ de puncte, $C=2$.
• Pentru teste valorând $40$ de puncte, $C=3$.

Exemplul 1

kpower.in

1
3 19
1 27 9 17 21 3 1 27 3 9 81 78 56 1 3 9 1 81 9

kpower.out

81

Explicație

$k$ este $3$, iar cel mai mare număr din șir care este putere a lui $3$ este $81$.

Exemplul 2

kpower.in

2
3 19
1 27 9 17 21 3 1 27 3 9 81 78 56 1 3 9 1 81 9

kpower.out

6

Explicație

Secvențele kpower din șir sunt $(1,27,9)$, $(3, 1, 27, 3, 9, 81)$ și $(1, 3, 9, 1, 81, 9)$. Lungimea maximă a unei secvențe kpower este $6$.

Exemplul 3

kpower.in

3
3 19
1 27 9 17 21 3 1 27 3 9 81 78 56 1 3 9 1 81 9

kpower.out

124

Explicație

Dintre cele două secvențe kpower de lungime maximă, cea dintâi are suma numerelor maximă: $3+1+27+3+9+81=124$.