Maximal Binary Number Transformation

We are given a set of n operations and each operation is represented by a string \(T_i\) of length \(m\) consisting of the characters 0, 1 and -. For any binary string \(S\) of length \(m\) (with characters \(S_1S_2\cdots S_m\)), an operation \(f_i\) transforms \(S\) into \(S'\) according to \(T_i\) as follows:

• If \(T_{i,j} = 0\), then \([f_i(S)]_j = 0\).
• If \(T_{i,j} = 1\), then \([f_i(S)]_j = 1\).
• If \(T_{i,j} = -\), then \([f_i(S)]_j = S_j\) (i.e. the \(j\)th bit is preserved).

You are also given an integer \(q\) (number of queries). For each query, you are given an initial binary string \(S\) of length \(m\). You can apply the operations arbitrarily many times (each operation may be used any number of times and in any order). Let the final obtained string be \(S'\), which is interpreted as a binary number (with \(S_1\) being the most significant bit). Your goal is to obtain the maximum possible binary number.

Observation: When applying an operation the bits that are updated (i.e. where \(T_{i,j}\) is 0 or 1) will overwrite the previous value. In order to maximize the final binary number, we want each bit to be 1 if possible. However, be careful: if an operation sets one bit to 1 while forcing another bit to 0, then you must ensure that the bit forced to 0 can later be recovered (i.e. set to 1 by some operation that does not spoil already fixed bits). The key is that when you want to update a bit to 1 at position \(j\) as the final change for that position, you can only use an operation \(f_i\) with \(T_{i,j} = 1\) if for every previously fixed (more significant) bit \(k<j\) that is desired to be 1, the operation does not overwrite it (i.e. either \(T_{i,k} = -\) or \(T_{i,k} = 1\)).

A greedy strategy from the most significant bit to the least significant bit ensures that once a bit is fixed to 1 it is not spoiled by later operations. Formally, for each bit \(j\) (\(1 \le j \le m\)) let the answer \(S'_j\) be determined as follows:

[ S'j = \begin{cases} 1, & \text{if } S_j = 1 \text{ or there exists an operation } T_i \text{ such that } T{i,j}=1 \text{ and for every } k<j \text{ with } S'k=1, ; T{i,k}\in{-,1};\ 0, & \text{otherwise.} \end{cases} ]

Output the final binary string \(S'\) for each query.

inputFormat

The input begins with two integers \(n\) and \(m\) (the number of operations and the length of strings, respectively).

Then follow \(n\) lines, each containing a string \(T_i\) of length \(m\), consisting of characters 0, 1, or -.

Next is an integer \(q\) representing the number of queries. Each of the following \(q\) lines contains a binary string \(S\) of length \(m\) (consisting of 0 and 1) – the initial string for that query.

Note: \(S_1\) is the most significant bit.

outputFormat

For each query, print the maximal binary string \(S'\) (of length \(m\)) that can be obtained by applying the operations arbitrarily many times. The string should represent the maximum possible binary number.

sample

2 2
1-
-1
2
00
10

11
11