Shortest Missing Subsequences

Given a string $s$, a 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$: the characters of $t$ need not be contiguous in $s$, but they must appear in the same order as they do in $s$.

For a given subset $v$ of the lowercase English letters from 'a' to 'z', a string $u$ is a missing subsequence of a string $s$ if $u$ is not a subsequence of $s$, and every character of $u$ and every character of $s$ belongs to $v$. A shortest missing subsequence of $s$ is a missing subsequence of $s$ whose length is the smallest among all missing subsequences of $s$.

You are given a set of English letters, a target string made up of characters from that set, and a list of query strings made up of characters from that set. For each query string, determine whether it is a shortest missing subsequence of the target string.

The first line contains a string $v$ ($1 \le |v| \le 26$) of lowercase letters in lexicographical order. Each letter appears at most once. This is the set of letters.

The second line contains a string $s$ ($1 \le |s| \le 10^6$; $s$ contains only letters from $v$). This is the target string.

The third line contains an integer $n$ ($1 \le n \le 10^6$), the number of queries.

Each of the next $n$ lines contains a string $q$ ($1 \le |q| \le 10^6$; $q$ contains only letters from $v$). These are the query strings. The sum of the lengths of all query strings does not exceed $10^6$.

Output $n$ lines. On each line, output $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.