비밀 메시지

베시가 소들을 이끌고 탈출을 시도하고 있습니다. 서로 정보를 주고받기 위해 소들은 비밀 이진(0과 1) 메시지를 보냅니다.

한 첩자가 $M$ ($1 \le M \le 5 \times 10^4$)개의 비밀 이진 메시지 각각에서 앞쪽 $b_i$ ($1 \le b_i \le 10^4$)개의 비트를 가로챘습니다.

또한 그는 소들이 사용한다고 추정되는 부분 암호 $N$ ($1 \le N \le 5 \times 10^4$)개의 목록을 만들었습니다. 암호 $j$에 대해서는 앞쪽 $c_j$ ($1 \le c_j \le 10^4$)개의 비트만 알고 있습니다.

메시지와 암호는 한쪽이 다른 쪽의 접두사(prefix)일 때 일치한다고 합니다. 즉 첫 번째 비트부터 두 문자열 중 더 짧은 쪽의 길이까지 모든 비트가 같으면 일치입니다. 각 암호 $j$에 대해, 가로챈 $M$개의 메시지 중 몇 개가 그 암호와 일치하는지 구하세요.

입력에 등장하는 비트의 총 개수(모든 $b_i$와 모든 $c_j$의 합)는 $5 \times 10^5$를 넘지 않습니다.

• 첫째 줄: 두 정수 $M$과 $N$.
• 둘째 줄부터 $M+1$번째 줄까지: $i+1$번째 줄은 가로챈 메시지 $i$를 나타내며, 정수 $b_i$ 다음에 $b_i$개의 비트(각각 $0$ 또는 $1$)가 공백으로 구분되어 주어집니다.
• $M+2$번째 줄부터 $M+N+1$번째 줄까지: $M+j+1$번째 줄은 암호 $j$를 나타내며, 정수 $c_j$ 다음에 $c_j$개의 비트(각각 $0$ 또는 $1$)가 공백으로 구분되어 주어집니다.

• $1$번째 줄부터 $N$번째 줄까지: $j$번째 줄에는 암호 $j$와 일치하는 가로챈 메시지의 개수를 정수 하나로 출력합니다.

네 개의 메시지 $010$, $1$, $100$, $110$과 다섯 개의 암호 $0$, $1$, $01$, $01001$, $11$을 생각해 봅시다.

• 암호 $0$은 $010$하고만 일치합니다: $1$개.
• 암호 $1$은 $1$, $100$, $110$과 일치합니다: $3$개.
• 암호 $01$은 $010$하고만 일치합니다: $1$개.
• 암호 $01001$은 $010$하고만 일치합니다($010$이 $01001$의 접두사): $1$개.
• 암호 $11$은 $1$과 $110$하고 일치합니다: $2$개.