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 represent