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.

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.

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

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 $ .