题目描述

你正在计划一次环游世界的旅行。为此，你在手机上安装了一个包含 $n$ 首歌的音乐应用，歌曲编号为 $1$ 到 $n$。

应用最初会为这 $n$ 首歌生成一个播放列表，以 $1, 2, \ldots, n$ 的一个排列形式表示，记为 $a_1, a_2, \ldots, a_n$。这些歌曲会按照 $a_1, a_2, \ldots, a_n$ 的顺序播放：$a_1$ 首先播放，接着是 $a_2$，依此类推。播放列表是无限循环的：每当 $a_n$ 播放完毕后，又会从 $a_1$ 开始。

每当当前歌曲播放结束后，下一首歌会自动播放。在一首歌尚未结束前，你也可以按下“跳过”按钮立即跳至列表中下一首歌。

你希望按照 $b_1, b_2, \ldots, b_n$ 这个期望排列完整听完这 $n$ 首歌。也就是说，你希望通过适当按“跳过”按钮的次数，使得你完整听到的第 $1$ 首歌是 $b_1$，第 $2$ 首是 $b_2$，……，第 $n$ 首是 $b_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$ 首歌。

输入格式

第一行包含两个整数 $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$ 行，每行包含三个整数 $c, x, y$（$c \in \{1, 2\}$，$1 \le x < y \le n$），表示第 $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$ 次跳过。

由 ChatGPT 5 翻译