Description

由于行为不端，Byteasar 被要求计算一个神秘且棘手的布尔值函数 $F(x,y)$，该函数定义在一对正整数序列 $x=(x_1,x_2,\cdots,x_n)$ 和 $y=(y_1,y_2,\cdots,y_n)$ 上，如下所示：

• 布尔函数 $F(x, y)$
• 如果 $W(x) \neq W(y)$ 则返回 $0$
• 否则如果 $|W(x)|=|W(y)|=1$ 则返回 $1$
• 否则返回 $F(p(x), p(y)) \wedge F(s(x), s(y))$。

其中：

• $W(x)$ 表示序列 $x$ 的成员集合（元素的顺序和重复无关紧要），
• $p(x)$ 表示序列 $x$ 的最长前缀（任意长度的初始部分），使得 $W(x) \neq W(p(x))$，
• $s(x)$ 表示序列 $x$ 的最长后缀（任意长度的末尾部分），使得 $W(x) \neq W(s(x))$，
• $\wedge$ 表示逻辑与，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)$ 值。

Input Format

标准输入的第一行包含一个整数 $k$ ($1\le k\le 13$)，表示要分析的序列对的数量。

接下来的 $3k$ 行包含测试用例的描述。

每个描述的第一行包含两个整数 $n$ 和 $m$ ($1\le n,m\le 100{,}000$)，用单个空格分隔，表示第一和第二序列的长度。

第二行包含 $n$ 个整数 $x_i$ ($1\le x_i\le 100$)，形成序列 $x$，以单个空格分隔。

第三行包含 $m$ 个整数 $y_i$ ($1\le y_i\le 100$)，形成序列 $y$，以单个空格分隔。

Output Format

输出应由正好 $k$ 行组成；第 $i$ 行（对于 $1\le i\le k$）应包含一个整数 - 0 或 1 - 表示第 $i$ 个测试用例的 $F(x, y)$ 值。

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

Hint

题面翻译由 ChatGPT-4o 提供。