Bessie ведёт коров на побег! Для этого они посылают друг другу секретные двоичные сообщения.

Умный контрразведчик Farmer John перехватил первые $b_{i}$ бит, $(1 \le b_{i} \le 10,000)$, каждого из $M$ сообщений, $(1 \le M \le 50,000)$.

Он составил список $N$ частичных кодовых слов, $(1 \le N \le 50,000)$, которые, по его мнению, используют коровы. Увы, знает лишь первые $c_{j}$ бит слова $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