AT_bogosortcontest_div1_b PerMutation

正整数 $ N, K, x \ (1 \leq x \leq N) $ 及び $ (1,2,\ldots,N) $ の順列 $ P=(P_1,P_2,\ldots,P_N) $ に対して、整数 $ f(P,K,x) $ を以下のように定義します。 > 長さ $ N+2 $ の数列 $ A=(A_0,A_1,\ldots,A_{N+1}) $ を用意し、すべての要素を $ 1 $ とする。 その後、 $ i=0, 1, \ldots, KN-1 $ の順に以下の操作を行う。 > > - $ j = P_{(i \bmod N) + 1} $ とする。 $ A_j $ を $ \lfloor\frac{A_{j-1}A_{j+1}}{A_j}\rfloor+1 $ に置き換える。 > > すべての操作を終えた後の $ A_x $ の値を $ f(P,K,x) $ とする。 正整数 $ N $ 及び $ (1,2,\ldots,N) $ の順列 $ P=(P_1,P_2,\ldots,P_N) $ が与えられます。 $ Q $ 個のクエリが与えられるので、与えられた順に処理してください。 各クエリは以下の $ 2 $ 種類のいずれかです。 - タイプ $ 1 $ ： `1 i j` の形式で与えられる。 $ P_i $ と $ P_j $ の値を入れ替える。 - タイプ $ 2 $ ： `2 K x` の形式で与えられる。現在の $ P $ に対する $ f(P,K,x) $ を $ 998244353 $ で割った余りを求める。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ ここで $ \mathrm{query}_k $ は $ k $ 番目のクエリであり、以下のいずれかの形式で与えられる。 > $ 1 $ $ i $ $ j $ > $ 2 $ $ K $ $ x $

タイプ $ 2 $ のクエリの個数を $ q $ として、 $ q $ 行出力せよ。 $ k $ 行目には $ k $ 番目のタイプ $ 2 $ のクエリに対する答えを出力せよ。

### Sample Explanation 1 はじめ、 $ P = (3,1,2,4) $ です。 $ 1 \sim 4 $ 番目のクエリでは、 $ P $ と $ K $ が共通なので、数列 $ A $ の変化も共通です。 各クエリでは $ A = (1,1,1,1,1,1) $ から始めて、以下のように操作が進みます。 - $ A_3 $ を $ \lfloor\frac{A_2A_4}{A_3}\rfloor + 1 = 2 $ に置き換える。 $ A = (1,1,1,2,1,1) $ となる。 - $ A_1 $ を $ \lfloor\frac{A_0A_2}{A_1}\rfloor + 1 = 2 $ に置き換える。 $ A = (1,2,1,2,1,1) $ となる。 - $ A_2 $ を $ \lfloor\frac{A_1A_3}{A_2}\rfloor + 1 = 5 $ に置き換える。 $ A = (1,2,5,2,1,1) $ となる。 - $ A_4 $ を $ \lfloor\frac{A_3A_5}{A_4}\rfloor + 1 = 3 $ に置き換える。 $ A = (1,2,5,2,3,1) $ となる。 したがって、 $ f(P, 1, 1) = 2, \ f(P, 1, 2) = 5, \ f(P, 1, 3) = 2, \ f(P, 1, 4) = 3 $ となります。 $ 5 $ 番目のクエリで $ P_2 $ と $ P_3 $ が入れ替わり、 $ P = (3,2,1,4) $ となります。 $ 6 \sim 9 $ 番目のクエリでは、 $ P $ と $ K $ が共通なので、数列 $ A $ の変化も共通です。 各クエリでは $ A = (1,1,1,1,1,1) $ から始めて、以下のように操作が進みます。 - $ A_3 $ を $ \lfloor\frac{A_2A_4}{A_3}\rfloor + 1 = 2 $ に置き換える。 $ A = (1,1,1,2,1,1) $ となる。 - $ A_2 $ を $ \lfloor\frac{A_1A_3}{A_2}\rfloor + 1 = 3 $ に置き換える。 $ A = (1,1,3,2,1,1) $ となる。 - $ A_1 $ を $ \lfloor\frac{A_0A_2}{A_1}\rfloor + 1 = 4 $ に置き換える。 $ A = (1,4,3,2,1,1) $ となる。 - $ A_4 $ を $ \lfloor\frac{A_3A_5}{A_4}\rfloor + 1 = 3 $ に置き換える。 $ A = (1,4,3,2,3,1) $ となる。 - $ A_3 $ を $ \lfloor\frac{A_2A_4}{A_3}\rfloor + 1 = 5 $ に置き換える。 $ A = (1,4,3,5,3,1) $ となる。 - $ A_2 $ を $ \lfloor\frac{A_1A_3}{A_2}\rfloor + 1 = 7 $ に置き換える。 $ A = (1,4,7,5,3,1) $ となる。 - $ A_1 $ を $ \lfloor\frac{A_0A_2}{A_1}\rfloor + 1 = 2 $ に置き換える。 $ A = (1,2,7,5,3,1) $ となる。 - $ A_4 $ を $ \lfloor\frac{A_3A_5}{A_4}\rfloor + 1 = 2 $ に置き換える。 $ A = (1,2,7,5,2,1) $ となる。 したがって、 $ f(P, 2, 1) = 2, \ f(P, 2, 2) = 7, \ f(P, 2, 3) = 5, \ f(P, 2, 4) = 2 $ となります。 ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq P_i \leq N $ - $ P_i \neq P_j \ (i \neq j) $ - $ 1 \leq Q \leq 2 \times 10^5 $ - タイプ $ 1 $ のクエリにおいて、 $ 1 \leq i < j \leq N $ - タイプ $ 2 $ のクエリにおいて、 $ 1 \leq K \leq 10^{18} $ - タイプ $ 2 $ のクエリにおいて、 $ 1 \leq x \leq N $ - 少なくとも $ 1 $ つのタイプ $ 2 $ のクエリが含まれる - 入力される数値はすべて整数