题目描述

在数学中，二面体群 $D_n$ 是正 $n$ 边形的对称群。旋转和反射都是 $D_n$ 的元素，实际上，二面体群的所有元素都可以表示为一系列旋转和反射的复合。$D_n$ 的元素通过置换顶点来作用于 $n$ 边形。例如，考虑一个正五边形，其顶点初始标记为 $1, 3, 5, 4, 2$（顺时针方向，从顶部开始）：

:::align{center} :::

将上述三个二面体作用（一次旋转、一次反射、再一次旋转）应用到五边形上，会得到以下顶点标记的重排：

$$1, 3, 5, 4, 2 \rightarrow 2, 1, 3, 5, 4 \rightarrow 2, 4, 5, 3, 1 \rightarrow 1, 2, 4, 5, 3.$$

你得到一个正 $n$ 边形的顶点标记（使用整数 $1$ 到 $n$，按顺时针顺序给出），以及一个待测试的序列。请判断是否存在一系列二面体群作用，使得在变换后的多边形上，该测试序列作为顶点标记的连续顺时针子序列出现。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 5 \cdot 10^4$），其中 $n$ 是多边形的顶点数，$m$ 是待测试序列的长度。

下一行包含 $n$ 个空格分隔的整数 $d$（$1 \le d \le n$）。这是多边形顶点的初始标记。保证 $1$ 到 $n$ 的每个整数恰好出现一次。

下一行包含 $m$ 个空格分隔的整数 $t$（$1 \le t \le n$）。这是待测试的序列。

输出格式

输出一个整数，如果存在一系列二面体群作用，使得测试序列作为初始多边形变换后顶点标记的连续子序列出现，则输出 $1$，否则输出 $0$。

3 3
1 2 3
1 3 2

1

3 1
1 2 3
1

1

4 2
1 2 3 4
1 3

0

4 4
1 2 3 4
2 3 4 1

1

4 4
1 2 3 4
3 2 1 4

1

5 3
1 3 5 4 2
2 1 3

1

5 4
1 3 5 4 2
2 1 5 3

0

提示

翻译由 DeepSeek V3.2 完成