题目描述

给出一个 $\texttt{01}$ 字符串 $S$，你可以进行任意次操作（包括 $0$ 次）。每次操作，你可以选择以下一种进行：

• 选择一个 $\texttt{01}$ 子串，将其替换为 $\texttt{1}$
• 选择一个 $\texttt{10}$ 子串，将其替换为 $\texttt{0}$

现在有 $q$ 个询问。对于每个询问，给定一个 $\texttt{01}$ 字符串 $t_i$。

你需要判断：是否存在一种操作方案，使得从初始字符串 $S$ 出发，经过若干次上述操作后，最终得到字符串 $t_i$。

每个询问相互独立。

输入格式

第一行一个正整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示字符串的长度。

第二行一个长度为 $n$ 的 $\texttt{01}$ 字符串。

第三行一个正整数 $q$（$1 \leq q \leq 2 \times 10^5$），表示询问串的数量。

接下来 $q$ 行，第 $i$ 行包含一个 $\texttt{01}$ 字符串 $t_i$（$1\leq|t_i|\leq2 \times 10^5$），表示第 $i$ 个询问（保证 $\sum |t_i| \leq 2 \times 10^5$）。

输出格式

对于每个询问输出一行：

• 如果存在一种操作方案，可以将 $S$ 变为 $t_i$，输出 $\texttt{YES}$
• 否则输出 $\texttt{NO}$

输出不区分大小写。例如，$\texttt{YES}$、$\texttt{Yes}$、$\texttt{yes}$ 和 $\texttt{yEs}$ 均会被判定为正确。

5
01010
4
0010
000
011
101

YES
YES
NO
NO

提示

对于第 $1$ 和 $2$ 个询问，存在 $\texttt{01010} \rightarrow \texttt{0010}$ 和 $\texttt{01010} \rightarrow \texttt{0010} \rightarrow \texttt{000}$ 的操作方式。