你正在规划一次环球旅行。为了这次旅行，你安装了一个音乐应用程序，其中包含 $n$ 首歌曲，编号为 $1$ 到 $n$。
起初，该应用程序以 $1, 2, \dots, n$ 的排列形式为这 $n$ 首歌曲生成一个播放列表，记为 $a_1, a_2, \dots, a_n$。它按照 $a_1, a_2, \dots, a_n$ 的顺序播放这 $n$ 首歌曲：首先播放歌曲 $a_1$，其次播放歌曲 $a_2$，依此类推。该播放列表是无限循环的：每次播放完歌曲 $a_n$ 后，它会重新从歌曲 $a_1$ 开始播放。
当当前歌曲播放完毕时，下一首歌曲会自动开始播放。在歌曲播放完毕之前，你可以按下“跳过”按钮，立即跳转到播放列表中的下一首歌曲。
你有一个期望的这 $n$ 首歌曲的听歌顺序，记为排列 $b_1, b_2, \dots, b_n$。这意味着你希望通过有策略地按下零次或多次“跳过”按钮，完整地听完这 $n$ 首歌曲，且听歌顺序为 $b_1, b_2, \dots, 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, \dots, b_n$。
输入格式
第一行包含两个整数 $n$ 和 $d$（$2 \le n \le 200\,000$；$2 \le d \le 200\,000$）。
第二行包含 $n$ 个整数，表示 $a_1, a_2, \dots, a_n$ 的初始值（$1 \le a_i \le n$；对于所有 $i \ne j$，有 $a_i \ne a_j$）。
第三行包含 $n$ 个整数，表示 $b_1, b_2, \dots, b_n$ 的初始值（$1 \le b_i \le n$；对于所有 $i \ne j$，有 $b_i \ne b_j$）。
接下来的 $d - 1$ 行中，第 $k$ 行包含三个整数 $c$、$x$ 和 $y$（$c \in \{1, 2\}$；$1 \le x < y \le n$），表示第 $k$ 天与第 $k + 1$ 天之间的更新。
输出格式
输出 $d$ 行，其中第 $k$ 行应包含第 $k$ 天所需的最小跳过次数。
样例
输入样例 1
4 3 1 4 2 3 3 2 1 4 1 3 4 2 1 3
输出样例 1
6 2 6
说明 1
在第一天，$(a_1, \dots, a_4) = (1, 4, 2, 3)$ 且 $(b_1, \dots, b_4) = (3, 2, 1, 4)$。你可以通过跳过 6 次，按期望的顺序完整听完这些歌曲：
- 歌曲 1 播放。跳过这首歌。
- 歌曲 4 播放。跳过这首歌。
- 歌曲 2 播放。跳过这首歌。
- 歌曲 3 播放。完整听完这首歌。
- 歌曲 1 播放。跳过这首歌。
- 歌曲 4 播放。跳过这首歌。
- 歌曲 2 播放。完整听完这首歌。
- 歌曲 3 播放。跳过这首歌。
- 歌曲 1 播放。完整听完这首歌。
- 歌曲 4 播放。完整听完这首歌。
在第二天，排列变为 $(a_1, \dots, a_4) = (1, 4, 3, 2)$ 且 $(b_1, \dots, b_4) = (3, 2, 1, 4)$。最少跳过次数为 2。
在第三天，排列变为 $(a_1, \dots, a_4) = (1, 4, 3, 2)$ 且 $(b_1, \dots, b_4) = (1, 2, 3, 4)$。最少跳过次数为 6。
输入样例 2
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
输出样例 2
16 26 21 20 6