Minimizing Error in Binary Pattern Matching

We are given (N) binary strings (called match items), each of length (L), and (M) distinct banned binary strings (called banned schemes) also of length (L). We need to find a binary string (S) (called a scheme) of length (L) that is not among the banned schemes, and minimizes the total error defined as follows. For each match item (T), its error value is the Hamming distance between (S) and (T) (i.e. the number of positions in which (S) and (T) differ). The goal is to minimize the sum of errors over all (N) match items.

A natural observation is that the error function is separable over positions. For each position (j) ((1 \le j \le L)), let the number of ones and zeros among the (N) match items be denoted by (c_1) and (c_0) respectively. Then if we choose (S_j = 0) the contribution at that position is (c_1), and if we choose (S_j = 1) the contribution is (c_0). Hence, if there were no bans, the bitwise optimal choice is to assign (S_j = 0) if (c_1 \le c_0) and (S_j = 1) otherwise. However, if this candidate scheme is banned, we must consider schemes that differ from the candidate in some bit positions. For each bit (j), let the extra cost of flipping the candidate bit be defined as: [ d_j = \begin{cases} c_0 - c_1, & \text{if candidate bit is } 0;\ c_1 - c_0, & \text{if candidate bit is } 1. \end{cases} ] Thus, for any scheme obtained from the candidate by flipping bits at positions in a set (S), its total error is [ \text{Total Error} = \text{Base Error} + \sum_{j\in S} d_j, ] where the base error is the error of the candidate scheme.

Your task is to output any valid scheme (that is not banned) with the minimum total error. It is guaranteed that at least one valid scheme exists.

inputFormat

The first line contains two integers (N) and (M) (the number of match items and the number of banned schemes).

Then follow (N) lines, each containing a binary string of length (L).

Then follow (M) lines, each containing a banned binary string of length (L> (all banned schemes are distinct).

It is guaranteed that (L) is the same for all strings and that at least one valid scheme exists.

outputFormat

Output a single binary string of length (L) representing the scheme with minimum total error that is not banned.

sample

3 1
101
010
101
000

101