题目描述
林克穿过果彭加沼泽,来到了壶洞窟的门口。但是一道机关挡住了他的去路,机关上的铭牌刻着:"只有解开迷题的人,方可进入洞窟探寻宝物。"
这个迷题是这样的:机关上有上下两串数字,它们分别是 1∼n 的排列。上方的数字串可以操作,而下方的不行。每次操作可以选取连续的 k 个数字,将它们翻转过来。由于机关有一定的使用寿命,操作至多可以进行
2×10
5次,允许不进行任何操作。只有两个序列变得完全相同,门才会开启。
形式化地说,有两个
1∼n的排列a
1,a
2,⋯,a
n
和 b
1,b
2,⋯,b
n,每次操作可以选取一个 l,满足 1≤l≤n−k+1,并将子串 a
l,a
l+1,⋯,a
l+k−1翻转过来。操作之后,a
1,a
2,⋯,a
n会变成 a
1,⋯,a
l−1,a
l+k−1,⋯,a
l+1,a
l,a
l+k,⋯,a
n。你需要用若干次操作使得 a
1=b
1,a
2=b
2,⋯,a
n=b
n。
请你帮助林克破解这道机关。
输入
第一行包含两个整数 n, k (2≤k≤n≤100
,k
为偶数),含义见题目描述。
第二行包含 n 个整数,第 i 个为 a
i(1≤a
i≤n),表示上方数字串的第 i 个数字。保证所有的 a
i两两不同。
第三行包含 n 个整数,第 i 个为 b
i(1≤b
i≤n),表示下方数字串的第 i 个数字。保证所有的 b
i两两不同。
输出
如果这道机关无解,输出一行一个整数 −1。
否则输出一种操作的方案。方案第一行,包含一个整数 c,表示操作的次数。c 应当满足
0≤c≤2×10
5。
接下来 c 行,第 i 行包含一个整数 l
i,表示第 i 步操作翻转了
a
li,a
li+1,⋯,a
li+k−1这个子串。l
i应当满足1≤l
i≤n−k+1。
如果有多种方案,输出任意一种即可。可以证明,只要有解,必然存在一种不超过
2×10
5
次操作的方案。
提示
样例输入二
6 4 2 5 4 1 6 3 1 2 3 4 5 6
样例输出二
2
第一个样例,a 的变化为 1,4,2,3→1,2,4,3→1,2,3,4。
第二个样例无解。