410744: GYM104095 H 林克与翻转排列

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. 林克与翻转排列time limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output......沼泽......花朵盛开的沼泽处......延续着新的道路.......——《塞尔达传说:织梦岛》

林克穿过果彭加沼泽,来到了壶洞窟的门口。但是一道机关挡住了他的去路,机关上的铭牌刻着:"只有解开迷题的人,方可进入洞窟探寻宝物。"

这个迷题是这样的:机关上有上下两串数字,它们分别是 的排列。上方的数字串可以操作,而下方的不行。每次操作可以选取连续k 个数字,将它们翻转过来。由于机关有一定的使用寿命,操作至多可以进行 2 × 105 次,允许不进行任何操作。只有两个序列变得完全相同,门才会开启。

形式化地说,有两个 的排列 a1, a2, ..., anb1, b2, ..., bn,每次操作可以选取一个 l,满足 1 ≤ l ≤ n - k + 1,并将子串 al, al + 1, ..., al + k - 1 翻转过来。操作之后,a1, a2, ..., an 会变成 a1, ..., al - 1, al + k - 1, ..., al + 1, al, al + k, ..., an。你需要用若干次操作使得 a1 = b1, a2 = b2, ..., an = bn

请你帮助林克破解这道机关。

Input

第一行包含两个整数 n, k (2 ≤ k ≤ n ≤ 100, k 为偶数),含义见题目描述。

第二行包含 n 个整数,第 i 个为 ai (1 ≤ ai ≤ n),表示上方数字串的第 i 个数字。保证所有的 ai 两两不同。

第三行包含 n 个整数,第 i 个为 bi (1 ≤ bi ≤ n),表示下方数字串的第 i 个数字。保证所有的 bi 两两不同。

Output

如果这道机关无解,输出一行一个整数  - 1

否则输出一种操作的方案。方案第一行,包含一个整数 c,表示操作的次数。c 应当满足 0 ≤ c ≤ 2 × 105

接下来 c 行,第 i 行包含一个整数 li,表示第 i 步操作翻转了 ali, ali + 1, ..., ali + k - 1 这个子串。li 应当满足 1 ≤ li ≤ n - k + 1

如果有多种方案,输出任意一种即可。可以证明,只要有解,必然存在一种不超过 2 × 105 次操作的方案。

ExamplesInput
4 2
1 4 2 3
1 2 3 4
Output
2
2
3
Input
6 4
2 5 4 1 6 3
1 2 3 4 5 6
Output
-1
Note

第一个样例,a 的变化为 1, 4, 2, 3 → 1, 2, 4, 3 → 1, 2, 3, 4

第二个样例无解。

加入题单

上一题 下一题 算法标签: