Filter

A database engine named ICPC (Instant Compression and Processing Codec) stores user activity records. Every record carries one integer user identifier. The records live in compressed data files, and one file can hold records of many users. Decompressing a file costs a lot of CPU time, so before it reads a file the engine needs a cheap check that decides whether the file might hold a record of a given user.

The engine runs that check with a Bloom filter. Each database fixes these integer parameters:

• $m$: the number of bits in a filter,
• $f$: the number of hash functions,
• $a_i$ for $0 \le i < f$: the multiplier of hash function $i$.

Every data file has one filter value, a vector of $m$ bits. Bit $j$ of that vector ($0 \le j < m$) is one if and only if the file holds a record of some user identifier $u_k$ for which

$j = (u_k \times a_i) \bmod m$

holds for some hash function $i$ ($0 \le i < f$).

The file may hold a record of user identifier $u_k$ if and only if bit $(u_k \times a_i) \bmod m$ of its filter value is one for every $i$ ($0 \le i < f$).

You are given the filter parameters, the filter value of each data file, and a query set of user identifiers. Report every data file that may hold a record of at least one identifier in the query set.

The first line contains the filter parameters $m$, $f$, and $a_i$ for $0 \le i < f$ ($1 \le m \le 1000$, $1 \le f \le 100$, $1 \le a_i < 2^{31}$).

The second line contains an integer $n$, the number of data files ($1 \le n \le 1000$). Each of the next $n$ lines contains the filter value of one data file in hexadecimal, a string of exactly $\lceil m/4 \rceil$ characters taken from 0123456789abcdef. The first character carries bits 0 to 3 of the value, ordered from the least significant bit of the hexadecimal digit to its most significant bit. The second character carries bits 4 to 7, the third carries bits 8 to 11, and so on. When $m \bmod 4 \ne 0$, the last character carries the remaining $m \bmod 4$ bits in its least significant bits and its other bits are zero.

The next line contains an integer $q$, the number of user identifiers in the query ($1 \le q \le 1000$), followed by the $q$ distinct identifiers $u_k$ of the query ($1 \le u_k < 2^{31}$).

Print on one line the integer $s$, the number of data files that may hold a record of at least one identifier of the query, followed by the zero-based numbers $d_t$ ($0 \le d_t < n$) of those files in increasing order. Separate every number on the line with a single space. When $s = 0$, print only $0$.