クエリで与えられる文字列を \(T\) とする。

明らかに次は必要条件である

• すべての \(i\) について、\(i\) bit目が \(T_i\) である \(S\) が存在する
  • 例: \(T\) が 1... なのに \(S\) が全て 0... だったら不可能である

これを深掘ると、次も必要条件であることがわかる

• すべての \(i, j\) について、\(i, j\) bit目が \(T_i, T_j\) である \(S\) が存在する
  • 例: \(T\) = 01... なのに \(S\) が全て 00...、10...、11... だったら不可能である

なぜならば、例えば 01... を生成するためには、\(3\) 個の文字列の少なくとも \(2\) 個は 0... で少なくとも \(2\) 個は .1... である。よって、\(1\) 個は 01... が元の文字列に含まれている必要があるからである。

そして、実はこれらが必要十分条件である。実際にこれらの条件を満たしていれば \(T\) が構築可能である。

abc... を作りたいとする

• 条件より、ab... と .bc... と a.c... が入力に存在する。これらをマージすれば abc... が作れる

abcd... を作りたいとする

• 上記の手順より、abc.. と ab.d... と a.cd... が作れる。これらをマージすれば abcd... が作れる

といった流れである。

あとはこの条件を高速に判定できれば良く、\(O(MN^2)\) 時間の前計算を行えばクエリごとに \(O(N^2)\) 、つまり合計 \(O((M + Q)N^2)\) 時間でこの問題が解ける。