AT_abc470_d [ABC470D] Inverse and Swap

You are given a permutation $ P = (P_1, \dots, P_N) $ of $ (1, \dots, N) $ . Process $ Q $ queries in order. There are two types of queries as follows: - `1 x y`: Swap the values of $ P_x $ and $ P_y $ . - `2`: Construct the permutation $ P' = (P'_1, \dots, P'_N) $ of $ (1, \dots, N) $ satisfying the following condition, and replace the values of $ P_1, \dots, P_N $ with $ P'_1, \dots, P'_N $ , respectively. (One can prove that such $ P' $ uniquely exists.) - $ P_{P'_i} = i $ for every integer $ i $ satisfying $ 1 \leq i \leq N $ . Output the values of $ P_1, \dots, P_N $ after processing all queries.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ P_1 $ $ P_2 $ $ \cdots $ $ P_N $ $ \mathrm{query}_1 $ $ \vdots $ $ \mathrm{query}_Q $ Here, $ \mathrm{query}_q $ represents the $ q $ -th query, and is given in one of the following two formats: > $ 1 $ $ x $ $ y $ > $ 2 $

Output the values of $ P_1, \dots, P_N $ after processing all queries, separated by spaces, on one line.

### Sample Explanation 1 At the point when each query has been processed, the values of $ P_1, \dots, P_N $ are as follows: - After processing the first query, $ P = (2,5,3,1,4) $ . - After processing the second query, $ P = (4,1,3,5,2) $ . - After processing the third query, $ P = (4,3,1,5,2) $ . - After processing the fourth query, $ P = (4,3,5,1,2) $ . - After processing the fifth query, $ P = (4,5,2,1,3) $ . ### Constraints - $ 2 \leq N \leq 5 \times 10^5 $ - $ 1 \leq Q \leq 5 \times 10^5 $ - $ (P_1, \dots, P_N) $ is a permutation of $ (1, \dots, N) $ . - $ 1 \leq x < y \leq N $ for queries of type $ 1 $ . - All input values are integers.