Tin mật

View as PDF

Submit solution


Points: 0.33 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
USACO December 2008 - Gold Division
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bessie định dẫn đàn bò đi trốn. Để đảm bảo bí mật, đàn bò liên lạc với nhau bằng cách tin nhắn nhị phân.

Từng là một nhân viên phản gián thông minh, John đã thu được ~M~ ~(1 \leq M \leq 50000)~ tin nhắn mật, tuy nhiên với tin nhắn ~i~ John chỉ thu được ~b_i~ ~(1 \leq b_i \leq 10000)~ bit đầu tiên.

John đã biên soạn ra ~1~ danh sách ~N~ ~(1 \leq N \leq 50000)~ các từ mã hóa mà đàn bò có khả năng đang sử dụng. Thật không may, John chỉ biết được ~c_j~ ~(1 \leq c_j \leq 10000)~ bit đầu tiên của từ mã hóa thứ ~j~.

Với mỗi từ mã hóa ~j~, John muốn biết số lượng tin nhắn mà John thu được có khả năng là từ mã hóa ~j~ này. Tức là với từ mã hóa ~j~, có bao nhiêu tin nhắn thu được có phần đầu giống với từ mã hóa ~j~ này. Việc của bạn là phải tính số lượng này.

Tổng số lượng các bit trong dữ liệu đầu vào (tổng các ~b_i~ và ~c_j)~ không quá ~500000~.

Input

  • Dòng ~1~: ~2~ số nguyên: ~M~ và ~N~
  • Dòng ~2~ ~\dots M+1~: Dòng ~i+1~ mô tả tin nhắn thứ ~i~ thu được, đầu tiên là ~b_i~ sau đó là ~b_i~ bit cách nhau bởi dấu cách, các bit có giá trị ~0~ hoặc 1.
  • Dòng ~M+2 \dots M+N+1~: Dòng ~M+j+1~ mô tả từ mã hóa thứ ~j~, đầu tiên là ~c_j~ sau đó là ~c_j~ bit cách nhau bởi dấu cách.

Output

  • Dòng ~1~ ...~N~: Dòng ~j~: Số lượng tin nhắn mà có khả năng là từ mã hóa thứ ~j~

Sample Input

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

Sample Output

1
3
1
1
2

Note

  • Giải thích ví dụ: Có ~4~ tin nhắn và ~5~ từ mã hóa. Các tin nhắn thu được có phần đầu là ~010~, ~1~, ~100~ và ~110~. Các từ mã hóa có phần đầu là ~0~, ~1~, ~01~, ~01001~, và ~11~.
  • Giải thích kết quả: ~0~ chỉ có khả năng là ~010 \rightarrow 1~ tin nhắn. ~1~ chỉ có khả năng là ~1~, ~100~, hoặc ~110 \rightarrow 3~ tin nhắn. ~01~ chỉ có thể là ~010 \rightarrow 1~ tin nhắn. ~01001~ chỉ có thể là ~010 \rightarrow 1~ tin nhắn. ~11~ chỉ có thể là ~1~ hoặc ~110 \rightarrow 2~ tin nhắn.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.