P2977 - 看起来很匹配

题目

P2977看起来很匹配

限制 : 时间限制 : 10000 MS 空间限制 : 262144 KB

评测说明 : 1s,256MB

问题描述

两个长度相同的数字序列 $x_1,\cdots,x_n$ 和 $y_1,\cdots,y_n$ ，如果满足以下几个条件，则“看起来很匹配”：

如果一个序列中两项相等，则另一个序列中这两项也相等。
即，如果 $x_i,x_j$ 相等则 $y_i,y_j$ 也相等；反之，如果 $y_i,y_j$ 相等则 $x_i,x_j$ 也相等。
如果一个序列中两项不相等，则相对大小关系和另一个序列中这两项的相对大小关系相同。
即，如果 $x_i$ 比 $x_j$ 小则 $y_i$ 也比 $y_j$ 小；反之，如果 $y_i$ 比 $y_j$ 小，则 $x_i$ 也比 $x_j$ 小。

现在有两个数字序列 $a_1,a_2,\cdots,a_n$ 和 $b_1,b_2,\cdots,b_m$ ，请找出 $\{a_i\}$ 的所有与 $\{b_i\}$ “看起来很匹配”的连续子序列，按递增顺序输出每个连续子序列的起始位置。

输入格式

第一行两个整数 $n,m$ 。

第二行 $n$ 个整数 $a_1,\cdots,a_n$ 。

第三行 $m$ 个整数 $b_1,\cdots,b_m$ 。

输出格式

如果一个都没有，输出 $-1$ ；否则以空格为间隔输出所有答案。

样例输入

样例输入1：
7 3
1 2 3 4 50 600 7000
1 2 3

样例输入2：
7 3
7 6 5 4 3 2 1
1 2 3

样例输入3:
11 4
3 8 3 4 8 4 7 4 6 4 5
1 3 1 2

样例输入4:
6 3
299 199 399 311 111 211
233 133 333

样例输出

样例输出1：
1 2 3 4 5

样例输出2：
-1

样例输出3:
1 4 6 8

样例输出4:
1

提示

$1\leq m<n\leq 10^5$
$1\leq 每个数\leq 10^9$