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 000
• 1 ≤ L ≤ 100 000
• 1 ≤ 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.