問題文

整数列の列 $S$ があります。$S=(S_{1},S_{2},\dots,S_{|S|})$ には長さが $1$ 以上 $K$ 以下ですべての要素が $1$ 以上 $M$ 以下である整数列全てが辞書順に並んでいます。

厳密には、$S$ は以下の条件を満たす整数列の列です。(このようなものは一意に定まることが証明できます。)

• $T$ を長さが $1$ 以上 $K$ 以下ですべての要素が $1$ 以上 $M$ 以下である整数列とするとき、$S_{i}=T$ となる正整数 $i$ はちょうど $1$ つである。
• $i<j$ であるとき、$S_{i}$ は $S_{j}$ よりも辞書順で小さい。

全ての要素が $1$ 以上 $M$ 以下である整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられるので、以下で説明される $Q$ 個のクエリに答えてください。

クエリは以下の $2$ 種類のうちのいずれかです。

• 1 l r : 整数 $l,r$ が与えられる。$B = (A_{l},A_{l+1},\dots,A_{r})$ としたとき、$S_{i}=B$ を満たす整数 $i$ の値を $998244353$ で割った余りを出力する。
• 2 x y : $A_x$ の値を $y$ に変更する。

制約

• 入力は全て整数である
• $1 \leq N,M \leq 10^5$
• $N \leq K \leq 10^9$
• $1 \leq Q \leq 10^5$
• $1 \leq A_i \leq M$
• $1$ 番目の形式のクエリにおいて、$1 \leq l \leq r \leq N$
• $2$ 番目の形式のクエリにおいて、$1 \leq x \leq N , 1 \leq y \leq M$
• $1$ 番目の形式のクエリが $1$ つ以上存在する

入力

入力は以下の形式で標準入力から与えられる。

$N\ M\ K\ Q$
$A_1\ A_2\ \dots\ A_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

ただし、$\text{query}_i$ は $i$ 番目のクエリを表しており、以下のいずれかの形式で与えられる。

$1\ l\ r$

$2\ x\ y$

出力

$1$ 番目のクエリの回数を $q$ 回として $q$ 行に出力せよ。$i$ 行目には、$i$ 個目の $1$ 番目のクエリに対する答えを出力せよ。

サンプル

5 2 5 4
1 1 1 1 2
1 1 5
2 3 2
1 1 5
1 2 4

6
13
18

7 8 9 10
1 8 4 6 3 6 4
1 1 7
1 2 7
1 3 5
2 7 2
2 3 5
1 3 7
1 1 4
2 1 1
2 5 6
1 4 7

17875752
143005991
70104797
89470686
18162836
109388948