알고리즘 가속

바이트아사르(Byteasar)는 벌로, 두 양의 정수 수열 $x = (x_1, \dots, x_n)$ 과 $y = (y_1, \dots, y_m)$ 에 대해 정의된 불(boolean) 함수 $F(x, y)$ 를 계산해야 한다. 함수는 다음과 같이 정의된다.

boolean F(x, y)
    if W(x) != W(y):              return 0
    else if |W(x)| = |W(y)| = 1:  return 1
    else:                         return F(p(x), p(y)) AND F(s(x), s(y))

여기서 각 기호의 뜻은 다음과 같다.

• $W(x)$ 는 수열 $x$ 에 나타나는 값들의 집합이다. (원소의 순서와 중복은 무시한다.)
• $p(x)$ 는 $W(p(x)) \neq W(x)$ 를 만족하는 $x$ 의 가장 긴 접두사(앞에서부터 잘라낸 임의 길이의 부분)이다.
• $s(x)$ 는 $W(s(x)) \neq W(x)$ 를 만족하는 $x$ 의 가장 긴 접미사(뒤에서부터 잘라낸 임의 길이의 부분)이다.
• $\land$ 는 논리곱(AND), $1$ 은 참, $0$ 은 거짓, $|z|$ 는 집합 $z$ 의 원소 개수를 뜻한다.

예를 들어 $x = (2, 3, 7, 2, 7, 4, 7, 2, 4)$ 이면 $W(x) = \{2, 3, 4, 7\}$, $p(x) = (2, 3, 7, 2, 7)$, $s(x) = (7, 2, 7, 4, 7, 2, 4)$ 이다.

정의를 그대로 따라 $F$ 를 계산하면 큰 입력에서는 터무니없이 느리므로, 최대한 빠르게 계산해야 한다. 여러 개의 수열 쌍 $(x, y)$ 를 읽어, 각 쌍에 대한 $F(x, y)$ 의 값을 출력하여라.

첫째 줄에 분석할 수열 쌍의 개수 $k$ ($1 \le k \le 13$) 가 주어진다. 이어지는 $3k$ 개의 줄에 각 쌍의 정보가 주어진다. 각 쌍마다 첫째 줄에는 두 수열 $x$ 와 $y$ 의 길이 $n$ 과 $m$ ($1 \le n, m \le 100{,}000$) 이 공백으로 구분되어 주어진다. 둘째 줄에는 수열 $x$ 를 이루는 $n$ 개의 정수 $x_i$ ($1 \le x_i \le 100$) 가, 셋째 줄에는 수열 $y$ 를 이루는 $m$ 개의 정수 $y_i$ ($1 \le y_i \le 100$) 가 각각 공백으로 구분되어 주어진다.

정확히 $k$ 개의 줄을 출력한다. $i$ 번째 줄 ($1 \le i \le k$) 에는 $i$ 번째 쌍에 대한 $F(x, y)$ 의 값인 $0$ 또는 $1$ 을 출력한다.