Bessie dẫn bò thử trốn thoát! Chúng gửi thông điệp nhị phân bí mật cho nhau.

Farmer John luôn khôn ngoan trong phản gián đã chặn $b_{i}$ bit đầu, $(1 \le b_{i} \le 10,000)$, của mỗi trong $M$ thông điệp, $(1 \le M \le 50,000)$.

Ông lập danh sách $N$ từ mã một phần, $(1 \le N \le 50,000)$, mà nghĩ bò dùng. Tiếc chỉ biết $c_{j}$ bit đầu của từ $j$, $(1 \le c_{j} \le 10,000)$.

Với mỗi từ $j$, tính số thông điệp bị chặn khớp nó, tức cùng các bit đầu.

Tổng bit đầu vào, tổng $b_{i}$ và $c_{j}$, không quá $500,000$.

Dữ liệu vào

• Dòng $1$: số nguyên $M$, $N$.

• Các dòng $2,\ldots,M+1$: dòng $i+1$ mô tả thông điệp $i$ bằng số nguyên $b_{i}$ rồi $b_{i}$ giá trị 0 hoặc 1 cách bằng khoảng trắng.

• Các dòng $M+2,\ldots,M+N+1$: dòng $M+j+1$ mô tả từ $j$ bằng số nguyên $c_{j}$ rồi $c_{j}$ giá trị 0 hoặc 1 cách bằng khoảng trắng.

Dữ liệu ra

• Các dòng $1,\ldots,M$: dòng $j$ là số thông điệp có thể khớp từ $j$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

1
3
1
1
2

Ghi chú

Bốn thông điệp, năm từ. Đầu thông điệp 010, 1, 100, 110; từ 0, 1, 01, 01001, 11.

0 chỉ khớp 010: $1$. 1 khớp 1, 100, 110: $3$. 01 chỉ 010: $1$. 01001 khớp 010: $1$. 11 khớp 1, 110: $2$.

Tác giả bài toán: David Benjamin và Jacob Steinhardt, 2008