Bessie は牛たちを率いて脱走を試みます！そのため秘密の二進メッセージを互いに送ります。

いつも賢い防諜役 Farmer John は $M$ 件、$(1 \le M \le 50,000)$、の各メッセージの先頭 $b_{i}$ ビット、$(1 \le b_{i} \le 10,000)$、を傍受しました。

牛が使うと思われる $N$ 個の部分的符号語、$(1 \le N \le 50,000)$、を一覧にしました。残念ながら符号語 $j$ の先頭 $c_{j}$ ビット、$(1 \le c_{j} \le 10,000)$、しか知りません。

各符号語 $j$ に一致する傍受メッセージ数、つまりメッセージと符号語の先頭ビットが同じである件数を求めてください。

入力の総ビット数、$b_{i}$ と $c_{j}$ の和は $500,000$ 以下です。

入力

• 行 $1$：整数 $M$、$N$。

• 行 $2,\ldots,M+1$：行 $i+1$ は傍受 $i$ を整数 $b_{i}$ と続く空白区切り $b_{i}$ 個の 0、1 で表します。

• 行 $M+2,\ldots,M+N+1$：行 $M+j+1$ は符号語 $j$ を整数 $c_{j}$ と続く空白区切り $c_{j}$ 個の 0、1 で表します。

出力

• 行 $1,\ldots,M$：行 $j$ は符号語 $j$ と一致しうるメッセージ数。

入出力例

入力 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

出力 1

1
3
1
1
2

注記

四メッセージ、五符号語です。先頭はそれぞれ 010、1、100、110 と、0、1、01、01001、11。

0 は 010 だけに一致：$1$ 件。1 は 1、100、110：$3$ 件。01 は 010 だけ：$1$ 件。01001 は 010：$1$ 件。11 は 1、110：$2$ 件。

問題作成者：David Benjamin と Jacob Steinhardt、2008