Let \(T\) be the string given in a query.

Clearly, the following is a necessary condition:

• For every \(i\), there exists some \(S\) whose \(i\)-th bit equals \(T_i\).
  • Example: if \(T\) is 1... but every \(S\) is 0..., then this is impossible.

Digging deeper, we find that the following is also a necessary condition:

• For every \(i\) and \(j\), there exists some \(S\) whose \(i\)-th and \(j\)-th bits equal \(T_i\) and \(T_j\), respectively.
  • Example: if \(T\) = 01... but every \(S\) is 00..., 10..., or 11..., then this is impossible.

This is because, for instance, in order to generate 01..., at least two of the three chosen strings must be 0... and at least two must be .1.... Thus, at least one of the original strings must be 01....

And in fact, these turn out to be a necessary and sufficient condition: if these conditions are satisfied, \(T\) can indeed be constructed.

Suppose we want to construct abc....

• By the condition, ab..., .bc..., and a.c... exist in the input. Merging these produces abc....

Suppose we want to construct abcd....

• By the procedure above, abc.., ab.d..., and a.cd... can be constructed. Merging these produces abcd....

And so on.

It remains to be able to determine this condition quickly. If we perform \(O(MN^2)\)-time precomputation, each query can be answered in \(O(N^2)\) time, so the problem can be solved in a total of \(O((M + Q)N^2)\) time.