Problem G
Shortest Missing Subsequences

Given a string s we say that string t is a Subsequence of s if t can be obtained from s by deleting zero or more characters of s. Note that t is not necessarily a substring of s—that is, t is not necessarily contiguous in s, but the characters of t appear in the same order as they do in s.

For a given subset, v, of the lowercase English alphabet characters from 'a' to 'z', we say that string u is a Missing Subsequence of another string s if u is not a Subsequence of s, but all characters in u and all the characters of s are in the set v. A Shortest Missing Subsequence of s is a Missing Subsequence of s with the smallest length among all Missing Subsequences of s.

Given a set of English alphabetic characters, a target string made up of characters from that set, and a list of query strings made up of characters from that set, determine if each of the query strings is a Shortest Missing Subsequence of the target string.

Input

The first line of input contains a string v (1 ≤ |v| ≤ 26) of lowercase letters, in lexicographical order. Each letter appears at most once. This is the set of alphabetic characters.

The next line of input contains a string s (1 ≤ |s| ≤ 10⁶, s only contains letters from v). This is the target string to be queried.

The next line contains an integer n ($1 ≤ n ≤ 10⁶). This is the number of queries.

Each of the next n lines contains a string q (1 ≤ |q| ≤ 10⁶, q only contains letters from v). These are the query strings. The sum of the lengths of all query strings will not exceed 10⁶.

Output

Output n lines, one for each query. On each line, output either 1 if the query string is a Shortest Missing Subsequence of the target string, or 0 if it is not. The outputs must be in the order of the input queries.

abc
abcccabac
3
cbb
cbba
cba

1
0
0