소 베시는 소들을 이끌고 탈출하려고 한다! 탈출을 하기 위해서 소들은 서로 비밀스러운 이진 암호를 주소 받는다. 또한 똑똑한 적군 스파이인 농부 존은 그들의 이진 암호 중 M (1<=M<=50000) 개에서 b_i (1<=b_i<=10000) 비트 만큼의 메시지를 낚아챘다.

그는 소들이 사용하고 있다고 생각하는 N (1<=N<=50000) 개의 부분적인 암호문구를 번역해냈지만, 슬프게도 그는 j 번째 암호문구의 처음 c_j (1<=c_j<=10000)개의 비트밖에 알지 못한다.

각각의 암호문구 j 에 대해서 그는 그가 낚아챈 이진 암호 중에서 얼마나 많은 메시지가 암호문구 j 와 일치하는지 알고 싶어한다. (암호문구 j 에 대해서 얼마나 많은 첫 비트들이 일치하는지 알고 싶어한다.) 당신의 일은 이 숫자를 세는 일이다. 총 입력의 비트 수는 500,000을 넘지 않는다.

입력

• 첫번째 줄에는 M 과 N 이 주어진다.
• 두번째 줄부터 M 개의 메시지 i 와 b_i 가 주어진다. (i 개의 b_i 가 주어진다.)
• M+N+1번째 줄부터 N 개의 암호문구 j 와 c_j 가 주어진다.

출력

입출력 예

입력

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
3
1
1
2

입력 설명

4개의 메시지; 5개의 암호문구.
낚아챈 메시지는 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 개 일치

출처:usaco 2008 DEC gold
번역: KangJ