patru

Numim putere4 un număr care poate fi scris sub forma $X^4$ + $Y^4$ (cu $X$ și $Y$ numere naturale nenule).

Fie un șir de $N$ numere naturale $T_1$, $T_2$, $\dots$, $T_N$. Suma unei secvențe de $K$ termeni ai șirului $T_i^4$ + $T_{i+1}^4$ + $\dots$ + $T_{i+K-1}^4$, se numește sumă4 dacă are ultima cifră $4$.

Cerință

Scrieți un program care citește numerele naturale nenule $N$ și $K$ și un șir de $N$ numere naturale nenule și determină:

• numărul de termeni din șirul dat care sunt putere4;
• numărul de secvențe de lungime $K$ ale șirului dat ce reprezintă o sumă4.

Date de intrare

Prima linie a fișierului patru.in conține două numere naturale $N$ și $K$, separate printr-un spațiu. Pe linia a doua se află $N$ numere naturale, separate prin câte un spațiu, ce reprezintă termenii șirului dat.

Date de ieșire

Fișierul de ieșire patru.out conține pe prima linie numărul de termeni ai șirului care sunt putere4. Pe linia a doua se găsește numărul de secvențe de tipul cerut.

Restricții și precizări

• $2 \leq K \leq N \leq 20 \ 000$
• termenii șirului sunt numere naturale mai mici sau egale cu $10^9$;
• prin secvență înțelegem o succesiune de elemente din șir aflate pe poziții consecutive;
• pentru afişarea corectă doar a primei valori se acordă $60\%$ din punctaj.

Exemplu

patru.in

7 5
1 2 17 15 23 19 17

patru.out

3
2

Explicație

Sunt trei elemente putere4 adică $2$, $17$ și $17$. Sunt $2$ secvențe sumă4 de lungime $5$ cu proprietatea din enunț (cea care începe pe poziția $1$ și cea care începe pe poziția $2$).