[POI2009] PRZ-Algorithm Speedup

你的任务是计算一个函数F(x, y)，其中x和y是两个正整数序列。F的定义如下： ```cpp boolean F(x, y) if W(x) ≠ W(y) then return 0 else if |W(x)| = |W(y)| = 1 then return 1 else return F(p(x), p(y)) AND F(s(x), s(y)). W(x)表示序列x中元素的集合。（元素的顺序和出现次数将被无视） p(x)表示序列x的最长前缀，满足：W(x) ≠ W(p(x)) s(x)表示序列x的最长后缀。满足：W(x) ≠ W(s(x)) |Z|表示集合Z中元素个数 ```

As a punishment for misbehaving, Byteasar is to calculate a certain mysterious and nasty Boolean-valued function $F(x,y)$, which is defined for a pair of positive integer sequences $x=(x_1,x_2,\cdots,x_n)$, $y=(y_1,y_2,\cdots,y_n)$ as follows: - boolean $F(x, y)$ - if $W(x)\neq W(y)$ then return $0$ - else if $|W(x)|=|W(y)|=1$ then return $1$ - else return $F(p(x), p(y)) \wedge F(s(x), s(y))$. Where: - $W(x)$ denotes the set of members of the sequence $x$ (order and repetitions of elements are insignificant), - $p(x)$ denotes the longest prefix (initial part of any length) of the sequence $x$, such that $W(x)\neq W(p(x))$, - $s(x)$ denotes the longest suffix (final part of any length) of the sequence $x$, such that $W(x)\neq W(s(x))$, - $\wedge$ denotes the logical conjunction, $1$ - true, $0$ - false, and $|z|$ - cardinality of set $z$. For example, for the sequence $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)$, $s(x)=(7,2,7,4,7,2,4)$. For very large data a programme calculating values of the function $F$ directly from definition is too slow by any standards. Therefore you are to make these calculations as fast as possible. Write a programme that reads several pairs of sequences $(x,y)$ from the standard input and prints out the values $F(x,y)$ on the standard output for every input pair.

The first line of the standard input contains one integer $k$ ($1\le k\le 13$) denoting the number of sequence pairs to analyse. Next $3k$ line hold descriptions of test cases. The first line of each description contains two integers $n$ and $m$ ($1\le n,m\le 100{,}000$) separated by a single space and denoting the lengths of the first and second sequence, respectively. The second line holds $n$ integers $x_i$ ($1\le x_i\le 100$) that form the sequence $x$, separated by single spaces. The third line holds $m$ integers $y_i$ ($1\le y_i\le 100$), that form the sequence $y$, separated by single spaces.

The output should consist of exactly $k$ lines; the $i$-th line (for $1\le i\le k$) should contain a single integer - 0 or 1 - the value of $F(x, y)$ for $i$-th test case.

2
4 5
3 1 2 1
1 3 1 2 1
7 7
1 1 2 1 2 1 3
1 1 2 1 3 1 3

0
1