P13922 [POCamp 2024] 魔影舞尽处 / Hårgalåten

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$ | $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$ | 无额外约束。 |