对于字符串 $s$，如果可以通过删除 $s$ 中的零个或多个字符得到字符串 $t$，则称 $t$ 是 $s$ 的一个子序列（Subsequence）。注意，$t$ 不一定是 $s$ 的子串——也就是说，$t$ 在 $s$ 中不一定是连续的，但 $t$ 中的字符在 $s$ 中出现的顺序必须一致。

对于给定的一个小写英文字母子集 $v$（包含从 ‘a’ 到 ‘z’ 的字符），如果字符串 $u$ 不是 $s$ 的子序列，且 $u$ 中的所有字符以及 $s$ 中的所有字符都在集合 $v$ 中，则称 $u$ 是 $s$ 的一个缺失子序列（Missing Subsequence）。$s$ 的最短缺失子序列（Shortest Missing Subsequence）是指在 $s$ 的所有缺失子序列中长度最短的那一个。

给定一组英文字母、一个由该集合中字符组成的字符串 $s$（目标字符串），以及一系列由该集合中字符组成的查询字符串，请判断每个查询字符串是否为目标字符串 $s$ 的最短缺失子序列。

输入格式

第一行输入包含一个字符串 $v$ ($1 \le |v| \le 26$)，由小写字母按字典序排列而成。每个字母最多出现一次。这是字母字符集。

第二行输入包含一个字符串 $s$ ($1 \le |s| \le 10^6$，$s$ 仅包含 $v$ 中的字母)。这是需要查询的目标字符串。

第三行包含一个整数 $n$ ($1 \le n \le 10^6$)。这是查询的数量。

接下来的 $n$ 行，每行包含一个字符串 $q$ ($1 \le |q| \le 10^6$，$q$ 仅包含 $v$ 中的字母)。这些是查询字符串。所有查询字符串的长度之和不超过 $10^6$。

输出格式

输出 $n$ 行，每行对应一个查询。如果查询字符串是目标字符串的最短缺失子序列，则输出 1，否则输出 0。输出顺序必须与输入查询的顺序一致。

样例

样例输入 1

abc
abcccabac
3
cbb
cbba
cba

样例输出 1

1
0
0