가장 짧은 부분열이 아닌 문자열

문자열 $s$에서 문자를 0개 이상 지워서 문자열 $t$를 얻을 수 있을 때, $t$를 $s$의 부분열이라고 한다. $t$는 $s$에서 연속할 필요는 없지만, $t$의 문자들은 $s$에서와 같은 순서로 나타나야 한다.

소문자 영어 알파벳 'a'부터 'z'까지의 부분집합 $v$가 주어졌을 때, 문자열 $u$의 모든 문자와 $s$의 모든 문자가 $v$에 속하면서 $u$가 $s$의 부분열이 아니면, $u$를 $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$을 출력한다. 출력은 입력된 질의 순서대로 이루어져야 한다.