Bessie führt die Kühe bei einem Fluchtversuch an! Dazu senden sie einander geheime Binärnachrichten.

Der stets schlaue Gegenspion Farmer John fing die ersten $b_{i}$ Bits, $(1 \le b_{i} \le 10,000)$, jeder von $M$ Nachrichten ab, $(1 \le M \le 50,000)$.

Er listete $N$ teilweise bekannte Codewörter, $(1 \le N \le 50,000)$, die die Kühe wohl verwenden. Leider kennt er nur die ersten $c_{j}$ Bits von Wort $j$, $(1 \le c_{j} \le 10,000)$.

Berechne für jedes Wort $j$, wie viele abgefangene Nachrichten passen, also dieselben Anfangsbits wie das Wort haben.

Die Gesamtzahl der Eingabebits, Summe der $b_{i}$ und $c_{j}$, ist höchstens $500,000$.

Eingabe

• Zeile $1$: ganze Zahlen $M$, $N$.

• Zeilen $2,\ldots,M+1$: Zeile $i+1$, Nachricht $i$ mit ganzzahligem $b_{i}$ und danach $b_{i}$ durch Leerzeichen getrennten 0- oder 1-Werten.

• Zeilen $M+2,\ldots,M+N+1$: Zeile $M+j+1$, Wort $j$ mit ganzzahligem $c_{j}$ und danach $c_{j}$ durch Leerzeichen getrennten 0- oder 1-Werten.

Ausgabe

• Zeilen $1,\ldots,M$: Zeile $j$, Anzahl Nachrichten, die Wort $j$ entsprechen können.

Beispiele

Eingabe 1

4 5
3 0 1 0
1 1
3 1 0 0
3 1 1 0
1 0
1 1
2 0 1
5 0 1 0 0 1
2 1 1

Ausgabe 1

1
3
1
1
2

Hinweis

Vier Nachrichten, fünf Wörter. Anfänge: Nachrichten 010, 1, 100, 110; Wörter 0, 1, 01, 01001, 11.

0 passt nur zu 010: $1$. 1 zu 1, 100, 110: $3$. 01 nur zu 010: $1$. 01001 zu 010: $1$. 11 zu 1, 110: $2$.

Aufgabenautoren: David Benjamin und Jacob Steinhardt, 2008