题目描述

给定集合

$$1, 2, 3, \dots, N$$

的两个排列：

$$P = (p_1, p_2, \dots, p_N), \qquad Q = (q_1, q_2, \dots, q_N).$$

从排列 $P$ 出发，可以反复执行如下操作：

选择两段相邻的、长度都为 $K$ 的连续元素块（其中 $K \le \frac{N}{2}$），交换这两段的位置，并且段内元素的相对顺序保持不变。

也就是说，若当前排列为

$$b_1, b_2, \dots, b_i, b_{i+1}, \dots, b_{i+K-1}, b_{i+K}, b_{i+K+1}, \dots, b_{i+2K-1}, \dots, b_N,$$

则可以把两段

$$b_i, b_{i+1}, \dots, b_{i+K-1}$$

和

$$b_{i+K}, b_{i+K+1}, \dots, b_{i+2K-1}$$

交换，得到新排列

$$b_1, b_2, \dots, b_i, b_{i+K}, b_{i+K+1}, \dots, b_{i+2K-1}, b_{i+1}, \dots, b_{i+K-1}, \dots, b_N.$$

原题此处的含义是：保持两段以外元素的相对位置不变，仅交换这两个长度为 $K$ 的相邻连续块。等价地，也可以理解为把区间

$$[b_i, b_{i+1}, \dots, b_{i+K-1}, b_{i+K}, \dots, b_{i+2K-1}]$$

变为

$$[b_{i+K}, b_{i+K+1}, \dots, b_{i+2K-1}, b_i, b_{i+1}, \dots, b_{i+K-1}].$$

当然，这个操作只有在

$$i + 2K - 1 \le N$$

时才合法。

请编写程序 perm，判断能否通过若干次这样的操作，把排列 $P$ 变成排列 $Q$。

输入格式

第一行输入两个正整数 $N$ 和 $K$。

第二行输入排列 $P$。

第三行输入排列 $Q$。

输出格式

输出一行一个整数：

• 输出 $1$ 表示可以从 $P$ 经过若干次操作到达 $Q$；
• 输出 $0$ 表示不可以。

数据范围

• $4 \le N \le 100000$
• $2 \le K \le \frac{N}{2}$
• 在 $50\%$ 的测试中，$N \le 1000$

样例 1

输入

6 2
5 6 1 2 3 4
3 6 5 2 1 4

输出

1

解释

第一次操作交换两段 $(6,1)$ 与 $(2,3)$，得到排列：

5 2 3 6 1 4

第二次操作交换两段 $(5,2)$ 与 $(3,6)$，即可得到目标排列。

样例 2

输入

4 2
3 4 2 1
4 3 2 1

输出

0

评分方式

测试点按组给分，只有整组测试全部通过时，才能获得该组分数。