题目内容

冷链库每个货位贴了一张三态标签，上面的整数会先写成三进制（不含前导零；0 就写成一位 0），再按货位顺序拼成一长串。质检时要把某一段货位的这串数字里所有 0 改成 2、所有 2 改成 0，再整串翻转，最后把得到的三进制数当成十进制读出。这个十进制数可能非常大，输出时对 998244353 取模。

货位上的数字会被改。共有 $q$ 次操作，分两种：

• 1 $l$ $r$：对闭区间 $[l,r]$ 做上面的质检，输出取模后的结果；
• 2 $p$ $x$：把第 $p$ 个货位上的数改成 $x$。

货位从 1 编号。

约束：

• 1 $\le$ $m,q$ $\le$ 100000
• 0 $\le$ $v_i,x$ $\le$ 1000000000
• 1 $\le$ $l$ $\le$ $r$ $\le$ $m$
• 1 $\le$ $p$ $\le$ $m$

输入描述

第一行两个整数 $m$、$q$（1 $\le$ $m,q$ $\le$ 100000），表示货位数和操作次数。

第二行 $m$ 个整数 $v_1,v_2,\ldots,v_m$（0 $\le$ $v_i$ $\le$ 1000000000），表示各货位上的初始数字。

随后 $q$ 行，每行一个操作：

• 1 $l$ $r$（1 $\le$ $l$ $\le$ $r$ $\le$ $m$）：查询；
• 2 $p$ $x$（1 $\le$ $p$ $\le$ $m$，0 $\le$ $x$ $\le$ 1000000000）：修改。

输出描述

对每个 1 操作，输出一行一个整数，即该段质检结果对 998244353 取模。

样例1

输入

4 3
1 5 0 8
1 1 4
1 2 4
1 1 1

输出

58
19
1

说明

四个数的三进制是 1、12、0、22。整段拼接为 112022，0/2 互换再翻转得到 002011，换成十进制是 58。只问第一位时，1 互换翻转仍是 1。

样例2

输入

1 3
0
1 1 1
2 1 3
1 1 1

输出

2
7

说明

0 写成 0，互换成 2。改成 3 后三进制是 10，互换翻转得到 21，即十进制 7。

样例3

输入

3 2
2 3 7
1 1 3
1 2 2

输出

102
7

说明

2、3、7 的三进制是 2、10、21，拼接 21021，互换再翻转得到 10210，十进制 102。只问中间的 3 时结果是 7。