Marian este programator la o firmă ce produce software antivirus şi a primit ca sarcină scrierea motorului de căutare al produsului. Firma fiind recent înfiinţată, analiştii i-au pus la dispoziţie doar un număr mic de viruşi cunoscuţi. Motorul va fi testat pe un şir de biţi extras dintr-un executabil, trebuind să producă o statistică care să conţină numărul de apariţii al fiecărui virus în şirul de biţi.
Cerinţă
Scrieţi un program pentru a-l ajuta pe Marian să obţină statistica cerută.
Date de intrare
Prima linie a fişierul de intrare virus.in conţine două numere naturale L şi N, separate printr-un spaţiu, L reprezentând mărimea şirului de biţi, iar N reprezentând numărul viruşilor cunoscuţi. A doua linie a fişierului conţine un şir de lungime L, format doar din caracterele 0 şi 1, reprezentând şirul de biţi. Următoarele 2*N linii conţin descrierea viruşilor puşi la dispoziţie de echipa de analişti. Fiecare virus este descris pe două linii consecutive; prima dintre aceste linii conţine un număr natural k reprezentând lungimea acestui virus (exprimată în biţi), iar a doua linie conţine un şir de lungime k, format doar din caracterele 0 şi 1, reprezentând descrierea lui.
Date de ieşire
Fişierul de ieşire virus.out va conţine exact N linii. Pe fiecare linie se va scrie o valoare naturală reprezentând numărul de apariţii al fiecărui virus cunoscut, în ordinea dată în fişierul de intrare.
Restricţii şi precizări
1 ≤ N ≤ 1 0001 ≤ L ≤ 100 0001 ≤ k ≤ 1 000- numărul total de apariţii nu va depăşi
1 000 000
Exemplu
virus.in
7 3
0110101
5
11111
1
0
3
101
virus.out
0
3
2
Explicații
Sunt 3 viruşi. Primul virus din fişier, 11111, nu apare în şirul de biţi , astfel se va scrie valoarea 0 pe prima linie a fişierului virus.out. Cel de-al doilea virus din fişier, 0, apare în şirul de biţi de 3 ori (poziţiile 1, 4 şi 6), astfel se va scrie valoarea 3 a doua linie a fişierului virus.out. Ultimul virus din fişier, 101, apare în şirul de biţi de 2 ori (începând cu poziţiile 3 şi 5), astfel se va scrie valoarea 2 pe a treia linie a fişierului virus.out.