Numim putere4 un număr care poate fi scris sub forma X4 + Y4 (cu X şi Y numere naturale nenule).
Fie un şir de N numere naturale T1, T2, ..., TN. Suma unei secvenţe de K termeni ai şirului T4i + T4i+1 + ... + T4i+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 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.
Exemple
patru.in
patru.out
Explicaţii
7 5
1 2 17 15 23 19 17
3
2
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).