题目描述

Hårgalåten 是一首瑞典民歌，讲述了魔鬼让一群年轻人跳舞直至死亡的故事。汤姆 喜欢 Hårgalåten，因此为他的管弦乐队编写了一段编曲。为了符合歌词的主题，汤姆以一种特殊的方式编排了这段音乐，使得任何人在错误的地方开始演奏都会永远被困住。

管弦乐队由 $N$ 名乐手组成，他们围成一圈，其中乐手 1 位于乐手 2 的左侧，乐手 2 位于乐手 3 的左侧，以此类推。请注意，乐手 $N$ 右侧的乐手是乐手 1。该编曲包含从 1 到 $M$ 编号的 $M$ 个小节。最初，有一个整数列表 $X_1, X_2, \dots, X_N$，其中 $X_i$ 表示乐手 $i$ 应该开始演奏的小节。演奏一个小节需要一秒钟，并且所有乐手同时演奏。乐手 $i$ 演奏完小节 $X_i$ 后，他们会查看其右侧乐手演奏的小节（即 $X_{i+1}$）。然后，乐手 $i$ 演奏小节 $f(X_{i+1})$，其中 $f(1), f(2), \dots, f(M)$ 是一个给定的函数。这个过程会反复进行。

换句话说，如果乐手 $i$ 在 $t$ 秒时演奏了小节 $x$，并且其右侧的乐手在 $t$ 秒时演奏了小节 $y$，那么乐手 $i$ 将在 $t + 1$ 秒时演奏小节 $f(y)$。

当所有乐手都至少演奏过所有小节一次时，歌曲结束。你的任务是确定，对于每个乐手，他们何时至少演奏过歌曲中的所有不同小节一次。有些乐手可能永远无法演奏所有小节，在这种情况下，管弦乐队将不得不无限期地演奏下去。

输入格式

输入的第一行包含整数 $N$ 和 $M$（$1 \le N, M \le 3 \cdot 10^5$），分别表示乐手数量和小节数量。

第二行包含 $N$ 个整数 $X_1,X_2,\dots ,X_N$，其中 $X_i$ 表示乐手 $i$ 应该开始演奏的小节。

第三行包含 $M$ 个整数 $f(1), f(2), \dots, f(M)$ ($1 \le f(i) \le M$)，这个函数用于确定乐手应该演奏哪个小节。

输出格式

如果某个乐手永远无法演奏所有小节，则输出 $-1$。否则，输出 $N$ 个整数 $t_1, t_2, \dots, t_N$，其中 $t_i$ 是乐手 $i$ 至少演奏过每个小节一次所需的时间（秒数）。

1 4
4
2 3 1 1

4

4 5
5 4 3 2
2 3 4 5 1

17 16 15 14 

3 4
1 4 1
2 3 2 4

-1

2 2
1 2
1 2

2 2

提示

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $10$ | $N = 1$ | | $2$ | $17$ | 对于所有 $1 \le i \le M$，$f(i) = i$。 | | $3$ | $16$ | $N, M \le 300$ | | $4$ | $22$ | $N, M \le 3000$ 且如果 $i \ne j$ 则 $f(i) \ne f(j)$。 | | $5$ | $9$ | $N, M \le 3000$ | | $6$ | $26$ | 无额外约束。 |