#750. Tin nhắn bí mật (Mã bài: SECRET)

Bessie đang lãnh đạo đàn bò bỏ trốn. Để liên lạc, những con bò gửi cho nhau các tin nhắn bí mật.

Các tin nhắn là dạng nhị phân, có tổng cộng tin nhắn. John, người có khả năng phản gián rất mạnh, đã chặn được một phần các tin nhắn này và biết được bit đầu tiên của tin nhắn nhị phân thứ . Anh ta cũng biết rằng đàn bò sử dụng mã mật khẩu. Tuy nhiên, anh ta chỉ biết được bit đầu tiên của mật khẩu thứ .

Đối với mỗi mật khẩu , anh ta muốn biết có bao nhiêu tin nhắn bị chặn khớp với nó. Nói cách khác, có bao nhiêu tin nhắn và mật khẩu này có cùng tiền tố. Tất nhiên, độ dài của tiền tố chung này phải bằng độ dài của chuỗi ngắn hơn trong hai chuỗi (tin nhắn và mật khẩu).

Dữ liệu:

• Dòng đầu tiên nhập vào và .
• Tiếp theo là dòng mô tả các tin nhắn bí mật, sau đó là dòng mô tả các mật khẩu.
• Mỗi dòng bắt đầu bằng một số nguyên biểu thị độ dài của tin nhắn hoặc mật khẩu, theo sau là nội dung của tin nhắn hoặc mật khẩu đó (là các chuỗi nhị phân).
• Tất cả các số đều được phân tách bằng dấu cách.

Kết quả:

• Gồm dòng, mỗi dòng in ra số lượng tin nhắn khớp với mật khẩu tương ứng.

Ví dụ:

Dữ liệu:

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

Kết quả:

1
3
1
1
2

Giới hạn: . Tổng số bit (tức ) sẽ không vượt quá .