Algorithm Speedup

As a punishment for misbehaving, Byteasar must evaluate a mysterious Boolean-valued function $F(x, y)$, defined for a pair of positive-integer sequences $x = (x_1, \dots, x_n)$ and $y = (y_1, \dots, y_m)$ as follows:

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))

Here:

• $W(x)$ is the set of values that occur in the sequence $x$ (the order and repetitions of elements do not matter).
• $p(x)$ is the longest prefix (an initial segment of any length) of $x$ such that $W(p(x)) \neq W(x)$.
• $s(x)$ is the longest suffix (a final segment of any length) of $x$ such that $W(s(x)) \neq W(x)$.
• $\land$ denotes logical conjunction, $1$ is true, $0$ is false, and $|z|$ is the number of elements of the set $z$.

For example, for $x = (2, 3, 7, 2, 7, 4, 7, 2, 4)$ we have $W(x) = \{2, 3, 4, 7\}$, $p(x) = (2, 3, 7, 2, 7)$, and $s(x) = (7, 2, 7, 4, 7, 2, 4)$.

Evaluating $F$ straight from its definition is hopelessly slow on large inputs, so you must compute it as fast as possible. Read several pairs of sequences $(x, y)$ and print the value of $F(x, y)$ for each pair.

The first line contains one integer $k$ ($1 \le k \le 13$), the number of sequence pairs to analyse. The pairs follow on the next $3k$ lines. For each pair, the first line holds two integers $n$ and $m$ ($1 \le n, m \le 100{,}000$), the lengths of $x$ and $y$. The second line holds the $n$ integers $x_i$ ($1 \le x_i \le 100$) forming $x$, and the third line holds the $m$ integers $y_i$ ($1 \le y_i \le 100$) forming $y$, each separated by single spaces.

Print exactly $k$ lines. The $i$-th line ($1 \le i \le k$) contains a single integer, $0$ or $1$, equal to the value of $F(x, y)$ for the $i$-th pair.