昨年 The ICPC Asia Pacific Championship に参加するため Hanoi を訪れたとき、有名なハノイの塔の問題を知りました。この問題には 3 本の棒と、半径がすべて異なる複数の円盤があり、円盤はどの棒にも通せます。棒には $1$ から $3$ の番号が付いています。どの時点でも各円盤はいずれかの棒に積まれ、各棒では上から下へ半径が増加する順に並ばなければなりません。1 手で、上の制約を破らない限り、ある棒の一番上の円盤を別の棒の一番上へ移動できます。目的は、最小の手数ですべての円盤を棒 $1$ に移動することです。
この有名な問題を拡張した問題を解きます。$n$ 個の整数からなる列 $p_1,p_2,\ldots,p_n$ があり、初期値が与えられます。
さらに $q$ 個の操作が与えられます。各操作は次のいずれかです。
変更操作：2 つの整数 $x$ と $y$ が与えられます。$p_x$ の値を $y$ に変更します。
求解操作：2 つの整数 $l$ と $r$ が与えられます。半径が $l,l+1,\ldots,r$ の $r-l+1$ 個の円盤についてハノイの塔を解きます。各 $l \le i \le r$ について、半径 $i$ の円盤は初めに棒 $p_i$ に積まれています。各棒の円盤の初期の順序は先述の制約を満たします。すべての円盤を棒 $1$ に移動する最小手数を $998\,244\,353$ を法として求めてください。
与えられた操作をすべて順に実行してください。
入力
最初の行には 2 つの整数 $n$ と $q$（$1 \le n \le 100\,000$、$1 \le q \le 100\,000$）が与えられます。2 行目には $p_1,p_2,\ldots,p_n$ の初期値を表す $n$ 個の整数（$1 \le p_i \le 3$）が与えられます。続く $q$ 行は、実行する順に操作を表します。各行の形式は次のいずれかです。
c x y（$1 \le x \le n$、$1 \le y \le 3$）：指定された整数 $x$ と $y$ に対して変更操作を行います。s l r（$1 \le l \le r \le n$）：指定された整数 $l$ と $r$ に対して求解操作を行います。
入力には少なくとも 1 つの求解操作が含まれます。
出力
各求解操作について順に、半径が $l,l+1,\ldots,r$ の円盤でハノイの塔を解く最小手数を $998\,244\,353$ を法として出力してください。
入出力例
入力 1
4 4 2 3 1 3 s 2 4 s 1 3 c 3 3 s 2 4
出力 1
6 2 7
注記
最初の操作では、半径 $2$、$3$、$4$ の円盤がそれぞれ棒 $3$、$1$、$3$ に積まれたハノイの塔を解きます。図 D.1 のように、すべての円盤を 6 手で棒 $1$ に移動できます。
図 D.1：すべての円盤を棒 $1$ に移す 6 手。網掛けの棒は直前の手で移動した棒を示します。
2 番目の操作では、半径 $1$、$2$、$3$ の円盤がそれぞれ棒 $2$、$3$、$1$ に積まれたハノイの塔を解きます。
4 番目の操作では、半径 $2$、$3$、$4$ の円盤がそれぞれ棒 $3$、$3$、$3$ に積まれたハノイの塔を解きます。