题目描述

题目译自 XVI OI Olimpiada Informatyczna – I etap Przyspieszenie algorytmu

Bajtazar 因故需计算一个复杂而神秘的逻辑函数 $\mathbf{F}(x, y)$，对于两个自然数序列 $x = (x_1, \ldots, x_n)$ 和 $y = (y_1, \ldots, y_m)$，其定义如下：

$ \begin{aligned} & \text { boolean } \mathbf{F}(x, y) \\ & \text { if } \mathbf{W}(x) \neq \mathbf{W}(y) \text { then return } \mathbf{0} \\ & \text { else if }|\mathbf{W}(x)|=|\mathbf{W}(y)|=1 \text { then return } 1 \\ & \text { else return } \mathbf{F}(\mathbf{p}(x), \mathbf{p}(y)) \wedge \mathbf{F}(\mathbf{s}(x), \mathbf{s}(y)) \text {. } \end{aligned} $

其中：

• $\mathbf{W}(x)$ 表示序列 $x$ 中所有数字的集合（忽略重复和顺序）。
• $\mathbf{p}(x)$ 是 $x$ 的最长前缀，使得 $\mathbf{W}(x) \neq \mathbf{W}(\mathbf{p}(x))$。
• $\mathbf{s}(x)$ 是 $x$ 的最长后缀，使得 $\mathbf{W}(x) \neq \mathbf{W}(\mathbf{s}(x))$。
• $\wedge$ 表示逻辑与，$1$ 表示真，$0$ 表示假，$|Z|$ 表示集合 $Z$ 的元素个数。

例如，对于序列 $x = (2, 3, 7, 2, 7, 4, 7, 2, 4)$，有：

$$\mathbf{W}(x) = {2, 3, 4, 7}, \quad \mathbf{p}(x) = (2, 3, 7, 2, 7), \quad \mathbf{s}(x) = (7, 2, 7, 4, 7, 2, 4) $$

直接按定义计算函数对于大数据量极慢。你的任务是尽可能加速计算此函数。

编写程序，从标准输入读取若干序列对 $(x, y)$，并在标准输出中打印每个序列对的 $\mathbf{F}(x, y)$ 值。

输入格式

第一行包含一个整数 $k$ $(1 \leq k \leq 13)$，表示需分析的序列对数量。

接下来的 $3k$ 行描述输入数据，每组测试数据占三行：

• 第一行包含两个整数 $n, m$ $(1 \leq n, m \leq 100000)$，表示序列 $x$ 和 $y$ 的长度。
• 第二行包含 $n$ 个整数 $x_i$ $(1 \leq x_i \leq 100)$，描述序列 $x$。
• 第三行包含 $m$ 个整数 $y_i$ $(1 \leq y_i \leq 100)$，描述序列 $y$。

输出格式

输出 $k$ 行，第 $i$ $(1 \leq i \leq k)$ 行包含一个整数 $0$ 或 $1$，表示第 $i$ 组测试数据的 $\mathbf{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