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