Fișierul intrare/ieșire	patru.in, patru.out	Sursă	ONI 2012 baraj gimnaziu
Autor	Marius Nicoli	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.2 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Patru (baraj gimnaziu)

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

Fie un șir de N numere naturale T₁, T₂, ..., T_N. Suma unei secvențe de K termeni ai șirului T⁴_i + T⁴_i+1 + ... + T⁴_i+K-1, 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

• 2 ≤ K ≤ N ≤ 20 000
• termenii șirului sunt numere naturale mai mici sau egale cu 1 miliard;
• prin secvență înțelegem o succesiune de elemente din șir aflate pe poziții consecutive.

Exemplu