ICPC Database Filtering with Bloom Filters

You are developing a high-performance database engine called ICPC (Instant Compression and Processing Codec) that stores user activity records. Each data file has a Bloom filter representing the set of user IDs present in that file. The Bloom filter is a binary vector of m bits. For each data file, a bit at position (j) (where (0 \le j < m)) is set to one if and only if there exists a user identifier (u_k) and some hash function index (i) (with (0 \le i < f)) such that the following equation holds: [ j = (u_k \cdot a_i) \bmod m ]

You are given the filter parameters and the bloom filter values for several data files, as well as a set of queried user identifiers. A data file may contain a record with user identifier (u_k) if and only if for every hash function index (i) ((0 \le i < f)) the bit at (j = (u_k \cdot a_i) \bmod m) in its Bloom filter is set to one. Your task is to determine which data files may contain a record corresponding to at least one of the queried user identifiers.

inputFormat

The input consists of multiple lines:

• The first line contains three integers: m (the number of bits in the Bloom filter), f (the number of hash functions), and n (the number of data files).
• The second line contains f integers: a₀, a₁, ..., a_f-1, which are the coefficients for the hash functions.
• The next n lines each contain a binary string of length m representing the Bloom filter of a data file. The first character corresponds to bit index 0.
• The following line contains a single integer q, the number of queried user identifiers.
• The last line contains q integers, representing the queried user identifiers.

For a given user identifier (u) and for each hash function (i) ((0 \le i < f)), compute the position [ j = (u \cdot a_i) \bmod m ] A data file may contain a record with user identifier (u) if and only if all the bits at the computed positions (for all (i)) in its Bloom filter are set to 1.

outputFormat

Output a single line containing the 0-indexed indices of the data files that may contain a record corresponding to at least one of the queried user identifiers. The indices should be printed in ascending order and separated by a single space. If no data file qualifies, print -1.

sample

10 2 3
3 7
1010101010
1111111111
0000000000
2
5 1

1