您正在计划环游世界。在这次旅行中,您安装了一个音乐应用程序,其中包含 $$$n$$$ 歌曲,编号从 $$$1$$$ 到 $$$n$$$。
最初,应用程序会以 $$$1, 2, \ldots, n$$$ 排列的形式为这些 $$$n$$$ 歌曲生成播放列表,用 $$$a_1, a_2, \ldots, a_n$$$ 表示。它按照 $$$a_1、a_2、\ldots、a_n$$$ 的顺序播放 $$$n$$$ 歌曲:首先播放歌曲 $$$a_1$$$,其次播放歌曲 $$$a_2$$$,依此类推。播放列表是 无限:每次播放歌曲 $$$a_n$$$ 后,都会从歌曲 $$$a_1$$$ 开始。
当前歌曲播放完毕后,自动开始播放下一首歌曲。在一首歌曲结束之前,您可以按 跳过 按钮可立即跳转到播放列表中的下一首歌曲。
您有 $$$n$$$ 歌曲的所需排列,用 $$$b_1、b_2、\ldots、b_n$$$ 表示。这意味着您想听 $$$n$$$ 歌曲 完整 按 $$$b_1、b_2、\ldots、b_n$$$ 的顺序,策略性地按跳过按钮零次或多次。换句话说,您希望完整收听(不跳过)的第一首歌曲是歌曲 $$$b_1$$$,第二首歌曲是歌曲 $$$b_2$$$,依此类推,直到第 $$$n$$$ 是歌曲 $$$b_n$$$。完整听完这些 $$$n$$$ 歌曲后,你就不再听了。
您使用此播放列表 $$$d$$$ 天。在每对连续的日子之间,您可以使用三个整数 $$$c$$$、$$$x$$$ 和 $$$y$$$ 更新排列,如下所示:
- 如果 $$$c = 1$$$,则交换 $$$a_x$$$ 和 $$$a_y$$$。
- 如果$$$c = 2$$$,则交换$$$b_x$$$ 和$$$b_y$$$。
请注意,每次更新的效果都会持续到随后的几天。
假设您每天从歌曲 $$$a_1$$$ 开始收听,请确定您需要按跳过按钮的最少次数,以便您完整收听的歌曲按此顺序为 $$$b_1、b_2、\ldots、b_n$$$。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$2 \le n \le 200\,000$$$; $$$2 \le d \le 200\,000$$$)。
第二行包含 $$$n$$$ 整数,表示 $$$a_1、a_2、\ldots、a_n$$$ 的初始值($$$1 \le a_i \le n$$$;$$$a_i \neq a_j$$$ 对于所有 $$$i \neq j$$$)。
第三行包含 $$$n$$$ 整数,表示 $$$b_1、b_2、\ldots、b_n$$$ 的初始值($$$1 \le b_i \le n$$$;$$$b_i \neq b_j$$$ 对于所有 $$$i \neq j$$$)。
接下来的 $$$d-1$$$ 行的第 $$$k$$$ 行包含三个整数 $$$c$$$、$$$x$$$ 和 $$$y$$$ ($$$c \in \{1, 2\}$$$; $$$1 \le x \lt y \le n$$$),表示第 $$$k$$$ 行和第 $$$k$$$ 行之间的更新第 $$$(k+1)$$$ 天。
输出
输出 $$$d$$$ 行,其中第 $$$k$$$ 行应包含第 $$$k$$$ 天的最小跳过次数。
示例
输入复制
4 3 1 4 2 3 3 2 1 4 1 3 4 2 1 3
输出复制
6 2 6
输入复制
7 5 4 7 1 2 6 5 3 2 6 5 1 4 3 7 1 2 5 2 6 7 1 6 7 2 1 5
输出复制
16 26 21 20 6
注意
示例输入/输出#1 的说明
第一天,$$$(a_1, \ldots, a_4) = (1, 4, 2, 3)$$$ 和 $$$(b_1, \ldots, b_4) = (3, 2, 1, 4)$$$。您可以按所需顺序完整收听这些歌曲,并跳过 $$$6$$$:
- 播放歌曲 $$$1$$$。跳过这首歌。
- 播放歌曲 $$$4$$$。跳过这首歌。
- 播放歌曲 $$$2$$$。跳过这首歌。
- 播放歌曲 $$$3$$$。完整地听这首歌。
- 播放歌曲 $$$1$$$。跳过这首歌。
- 播放歌曲 $$$4$$$。跳过这首歌。
- 播放歌曲 $$$2$$$。完整地听这首歌。
- 播放歌曲 $$$3$$$。跳过这首歌。
- 播放歌曲 $$$1$$$。完整地听这首歌。
- 播放歌曲 $$$4$$$。完整地听这首歌。
第二天,排列为 $$$(a_1, \ldots, a_4) = (1, 4, \mathbf{3}, \mathbf{2})$$$ 和 $$$(b_1, \ldots, b_4) = (3, 2, 1, 4)$$$。最少跳过次数为 $$$2$$$。
第三天,排列为 $$$(a_1, \ldots, a_4) = (1, 4, 3, 2)$$$ 和 $$$(b_1, \ldots, b_4) = (\mathbf{1}, 2, \mathbf{3}, 4)$$$。最少跳过次数为 $$$6$$$。