格子可以分成三类：
- 未翻开的红色格子。
- 已翻开的格子。
- 未翻开的其他格子。
我们要找到一个单词的前缀包含所有第 1 类格子，且不包含第 3 类格子。
问题转化为，给定 $n$ 个长度为 $25$ 的 $\texttt{01}$ 串，每次询问找到一个串能够匹配带通配符的形如 $\texttt{01?}$ 的模式串 。并且模式串中 $\texttt1$ 的数目不超过 $9$。
首先容易判断解是否存在。如果模式串不包含 $\texttt1$，则字符串个数是一个子集和，那么枚举 $\texttt1$ 改成 $\texttt0$ 或 $\texttt{?}$ 后容斥即可算出满足条件的字符串个数。这样的复杂度为 $O(n+2^{25}\cdot 25+q\cdot 2^9)$。
要算出具体是哪个串，可以逐位确定 $\texttt?$ 的取值。但注意到检查是否存在匹配的串的复杂度与 $\texttt 1$ 的数目有关，因此我们应该优先检查 $\texttt0$，如果存在该位为 $\texttt0$ 的串那么就取 $\texttt0$，否则计算时可以直接把这一位当作 $\texttt?$。询问一次的复杂度变为 $O(2^9\cdot 25)$。