Cifra de control a unui număr natural x se obține astfel:

• dacă numărul x are o singură cifră, atunci cifra de control a lui x este egală cu x;
• dacă numărul x are cel puțin două cifre, atunci se calculează suma cifrelor lui x (să o notăm cu s); cifra de control a lui x va fi egală cu cifra de control a lui s.

De exemplu, cifra de control a numărului 175 este egală cu cifra de control a numărului 13 (1 + 7 + 5), care este egală cu 4 (1+3).

Fie x[1], x[2], ..., x[N] un șir de N numere naturale. Două poziții i și j, cu 1 ≤ i ≤ j ≤ N, definesc secvența [i, j] care va conține numerele x[i], x[i + 1], ..., x[j].

O secvență [i, j] cu proprietatea că suma tuturor elementelor din secvență are cifra de control egală cu 9 o vom denumi secv9.

Cerința

Scrieţi un program care, cunoscând N, numărul de elemente din șir, respectiv x[1], x[2], ..., x[N], elementele din șir, rezolvă următoarele două cerințe:

• afișează lungimea maximă a unei secvențe secv9;
• afișează numărul de secvențe secv9 din șir.

Date de intrare

Fișierul de intrare secv9.in conține pe prima linie două numere naturale C și N, reprezentând cerința care trebuie rezolvată (1 sau 2), respectiv lungimea șirului. Următoarea linie conține N numere naturale x[1], x[2], ..., x[N], separate prin câte un spațiu, reprezentând elementele din șir.

Date de ieșire

Fișierul de ieșire secv9.out va conține pe prima linie un singur număr natural, reprezentând răspunsul la cerința C din fișierul de intrare.

Restricții și precizări

• 1 ≤ N ≤ 1.000.000
• 0 ≤ x[i] ≤ 1000, pentru oricare 1 ≤ i ≤ N.
• Se garantează pentru toate datele de test că există cel puțin o secvență secv9.
• Pentru 8 puncte, C=1 și 1 ≤ N ≤ 1000
• Pentru 10 puncte, C=1 și 1001 ≤ N ≤ 5000
• Pentru 22 puncte, C=1 și 5001 ≤ N ≤ 1.000.000
• Pentru 12 puncte, C=2 și 1 ≤ N ≤ 1000
• Pentru 15 puncte, C=2 și 1001 ≤ N ≤ 5000
• Pentru 33 puncte, C=2 și 5001 ≤ N ≤ 1.000.000

Exemplul 1:

secv9.in

1 7
1 7 6 1 11 5 9

secv9.out

3

Explicație

Sunt două secvențe secv9 în șirul dat:

• secvența [3,5], alcătuită din numerele 6, 1 și 11, are suma termenilor 18 = 6 + 1 + 11, deci cifra de control este 9;
• secvența [7,7], alcătuită din numărul 9, are suma termenilor 9, deci cifra de control este 9.

Lungimea maximă a unei secvențe secv9 este 3.

Exemplul 2:

secv9.in

2 7
1 7 6 1 11 5 9

secv9.out

2

Explicație

Sunt două secvențe secv9 în șir: [3,5] și [7,7].