CF2206J.Worldwide Playlist

You are planning a trip around the world. For this trip, you have installed a music app containing $n$ songs, numbered from $1$ to $n$.

Initially, the app generates a playlist for these $n$ songs in the form of a permutation of $1, 2, \ldots, n$, denoted by $a_1, a_2, \ldots, a_n$. It plays the $n$ songs in the order $a_1, a_2, \ldots, a_n$: song $a_1$ plays first, song $a_2$ plays second, and so on. The playlist is infinite: each time after song $a_n$ plays, it starts all over from song $a_1$.

The next song starts playing automatically when the current song finishes. Before a song finishes, you may instead press a skip button to immediately jump to the next song in the playlist.

You have a desired permutation of the $n$ songs, denoted by $b_1, b_2, \ldots, b_n$. This means that you want to listen to $n$ songs in full in the order of $b_1, b_2, \ldots, b_n$ by strategically pressing the skip button zero or more times. In other words, you want the first song you listen to in full (not skipped) to be song $b_1$, the second to be song $b_2$, and so on, until the $n$-th is song $b_n$. After listening to these $n$ songs in full, you stop listening.

You use this playlist for $d$ days. Between each pair of consecutive days, you update the permutations using three integers $c$, $x$, and $y$ as follows:

• If $c = 1$, then you swap $a_x$ and $a_y$.
• If $c = 2$, then you swap $b_x$ and $b_y$.

Note that the effect of each update persists to subsequent days.

For each day, assuming you start listening from song $a_1$, determine the minimum number of times you need to press the skip button so that the songs you listen to in full are $b_1, b_2, \ldots, b_n$ in this order.

你正在计划一次环球旅行。为此，你安装了一个音乐应用程序，其中包含 $n$ 首歌曲，编号为 $1$ 到 $n$。

初始时，该应用为这 $n$ 首歌曲生成一个播放列表，形式为 $1, 2, \ldots, 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$（按此顺序）。

The first line of input contains two integers $n$ and $d$ ($2 \le n \le 200\,000$; $2 \le d \le 200\,000$).

The second line contains $n$ integers representing the initial values of $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$; $a_i \neq a_j$ for all $i \neq j$).

The third line contains $n$ integers representing the initial values of $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$; $b_i \neq b_j$ for all $i \neq j$).

The $k$-th of the next $d-1$ lines contains three integers $c$, $x$, and $y$ ($c \in {1, 2}$; $1 \le x \lt y \le n$), representing the update between the $k$-th and $(k+1)$-th days.

输入的第一行包含两个整数 $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$；对所有 $i \neq j$，有 $a_i \neq a_j$）。

第三行包含 $n$ 个整数，表示初始值 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le n$；对所有 $i \neq j$，有 $b_i \neq b_j$）。

接下来的 $d-1$ 行中，第 $k$ 行包含三个整数 $c$、$x$ 和 $y$（$c \in \{1, 2\}$；$1 \le x \lt y \le n$），表示第 $k$ 天与第 $k+1$ 天之间的更新操作。

Output $d$ lines, where the $k$-th line should contain the minimum number of skips for the $k$-th day.

输出 $d$ 行，其中第 $k$ 行应包含第 $k$ 天所需的最少跳过次数。

Explanation for the sample input/output #1

On the first day, $(a_1, \ldots, a_4) = (1, 4, 2, 3)$ and $(b_1, \ldots, b_4) = (3, 2, 1, 4)$. You can listen to these songs in full in the desired order with $6$ skips:

• Song $1$ plays. Skip this song.
• Song $4$ plays. Skip this song.
• Song $2$ plays. Skip this song.
• Song $3$ plays. Listen to this song in full.
• Song $1$ plays. Skip this song.
• Song $4$ plays. Skip this song.
• Song $2$ plays. Listen to this song in full.
• Song $3$ plays. Skip this song.
• Song $1$ plays. Listen to this song in full.
• Song $4$ plays. Listen to this song in full.

On the second day, the permutations are $(a_1, \ldots, a_4) = (1, 4, \mathbf{3}, \mathbf{2})$ and $(b_1, \ldots, b_4) = (3, 2, 1, 4)$. The minimum number of skips is $2$.

On the third day, the permutations are $(a_1, \ldots, a_4) = (1, 4, 3, 2)$ and $(b_1, \ldots, b_4) = (\mathbf{1}, 2, \mathbf{3}, 4)$. The minimum number of skips is $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$。