P2977 - 看起来很匹配

Problem

P2977看起来很匹配

Limits : Time Limit : 10000 MS Memory Limit : 262144 KB

Judgment Tips : 1s,256MB

Description

两个长度相同的数字序列 $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\}$ “看起来很匹配”的连续子序列，按递增顺序输出每个连续子序列的起始位置。

Input Format

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

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

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

Output Format

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

Sample Input

样例输入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

Sample Output

样例输出1：
1 2 3 4 5

样例输出2：
-1

样例输出3:
1 4 6 8

样例输出4:
1

Hint

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