問題文

正整数 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 で割った余りを求める。

制約

• 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 のクエリが含まれる
• 入力される数値はすべて整数

入力例 1

4
3 1 2 4
9
2 1 1
2 1 2
2 1 3
2 1 4
1 2 3
2 2 1
2 2 2
2 2 3
2 2 4

出力例 1

2
5
2
3
2
7
5
2

はじめ、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 となります。

入力例 2

5
3 4 5 2 1
15
1 4 5
1 3 5
2 8 1
2 10 1
2 10 4
2 3 3
2 8 5
1 2 3
2 6 4
2 8 1
1 3 4
2 4 3
1 2 3
2 6 2
2 4 5

出力例 2

1
2
7
10
1
7
1
1
11
2

入力例 3

10
2 3 8 9 10 5 4 7 6 1
20
2 100000 8
2 1000000 4
2 10000000 9
2 100000000 7
2 1000000000 6
2 10000000000 1
2 100000000000 1
2 1000000000000 7
1 5 9
1 7 8
1 6 10
2 10000000000000 5
1 2 7
2 100000000000000 6
2 1000000000000000 6
2 10000000000000000 2
2 100000000000000000 5
1 5 8
1 6 9
2 1000000000000000000 6

出力例 3

18
7
11
43
2
3
4
3
40
39
3
3
22
3