Lexicographically Minimal Support Sequence after XOR

Given a set \(S\) of \(n\) binary strings (each of length \(m\)) and \(q\) queries, the task is as follows. For a binary string \(w = w_1w_2\dots w_m\), define its support sequence \(\mathrm{supp}(w)\) as the increasing list of positions where \(w_i=1\). For example, \(\mathrm{supp}(001100110) = [3,4,7,8]\) and the all-zero string has support sequence \(\varepsilon\) (empty sequence).

For each query, you are given a binary string \(t\) (length \(m\)). You need to choose a subset \(T \subseteq S\) (possibly empty) so that if \(u = t \oplus \bigoplus_{v \in T} v\) (where \(\oplus\) denotes bitwise XOR), then among all possible strings obtainable in this way, the support sequence \(\mathrm{supp}(u)\) is lexicographically minimum.

Recall that for two sequences \(A\) and \(B\), we say \(A\) is lexicographically smaller than \(B\) if either \(A\) is a proper prefix of \(B\), or if at the first position \(p\) where they differ, \(A_p < B_p\). Note that the empty sequence is considered lexicographically smallest.

Observation: The XOR of a subset \(T\) is an element of the vector space \(W\) spanned by \(S\) over \(\mathbb{F}_2\). In other words, all candidates \(u\) lie in the affine space \(t+W = \{t\oplus x: x\in W\}\). It turns out that if \(t\in W\) then we may choose \(T\) so that \(u=\mathbf{0}\) (whose support sequence is empty, and hence lexicographically smallest). Otherwise, when \(t\notin W\) the problem reduces to finding the unique vector in the coset \(t+W\) whose support sequence is lexicographically minimal.

A key idea is to observe the following: For each position \(i\) (\(1 \le i \le m\)), note that the \(i^\text{th}\) coordinate of any vector in the coset \(t+W\) is fixed if no vector in \(W\) has a 1 in that coordinate. In that case the \(i^\text{th}\) bit of \(u\) must equal \(t_i\). Otherwise, when there is freedom at position \(i\) (i.e. some vector in \(W\) has a 1 in that coordinate), we are allowed to choose the \(i^\text{th}\) bit of \(u\) arbitrarily. Then the lexicographical minimality of the support sequence forces the following strategy:

• If \(t\in W\), output the all-zero string (which has an empty support sequence).
• If \(t\notin W\), then let \(i\) run from 1 to \(m\). For each coordinate \(i\):
  • If the \(i^\text{th}\) coordinate is fixed (i.e. no freedom because no vector in \(W\) has a 1 in that coordinate), then \(u_i = t_i\).
  • If there is freedom at coordinate \(i\), then we can choose \(u_i\) as follows:
    • If no 1 has yet appeared in \(u\) (i.e. the support sequence is still empty), we force \(u_i = 1\) (to make the first element as small as possible, since the smallest possible index is 1).
    • If a 1 has already appeared (i.e. the support sequence is nonempty), we set \(u_i = 0\) in order not to extend the support sequence unnecessarily.

Your task is to implement this strategy. Note that although the choices for free coordinates might seem independent, the structure of \(W\) (spanned by \(S\)) also restricts the possible values. In this problem, it suffices to note that a coordinate \(i\) is free if and only if there exists at least one string \(v \in S\) with \(v_i = 1\).

Input Format: The first line contains three integers \(n, m, q\) (the number of strings in \(S\), the length of each string, and the number of queries). Then follow \(n\) lines, each containing a 01 string of length \(m\). Then follow \(q\) lines, each containing a 01 string \(t\) of length \(m\) representing a query.

Output Format: For each query, output a 01 string \(u\) of length \(m\) that can be obtained as \(u = t \oplus (\bigoplus_{v\in T} v)\) for some subset \(T\subseteq S\) and whose support sequence is lexicographically minimal.

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\). The next \(n\) lines each contain a 01 string of length \(m\). The following \(q\) lines each contain a 01 string \(t\) of length \(m\).

outputFormat

For each query, output a single line containing the 01 string \(u\) of length \(m\) satisfying the conditions.

sample

2 3 3
110
010
101
000
011

101
000
101