24591번 - 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.

입력

The first line of input 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 alphabetic characters.

The next line of input contains a string $s$ (1ドル \le |s| \le 10^6,ドル $s$ only contains letters from $v$). This is the target string to be queried.

The next line contains an integer $n$ (1ドル \le n \le 10^6$). This is the number of queries.

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

출력

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.

제한

힌트