当前没有测试数据。

Description

定义：$a\oplus b=2\max\{a,b\},\ a\oplus b\oplus c=(a\oplus b)\oplus c$。

$1\ x\ v$：$a_x=a_x+v$。
$2\ l\ r$：求 $a_l\oplus a_{l+1}\oplus ...\oplus a_r$。

保证操作过程中 $|a_i|\leq 10^9$。

Format

Input

第一行两个个整数 $n,m\ (1\leq n,m\leq 10^6)$。

第二行 $n$ 个整数表示初始序列 $a_i\ (0\leq |a_i|\leq 10^9)$。

接下来 $m$ 行每个描述一个操作。

$1\ x\ v$：$a_x=a_x+v\ (0\leq |v|\leq 10^9)$。
$2\ l\ r$：求 $a_l\oplus a_{l+1}\oplus ...\oplus a_r\ (1\leq l\leq r\leq n)$。

答案对 $998244353$ 取模。

注意：是最终结果对 $998244353$ 取模，不是计算过程中对 $998244353$ 取模。

Output

对于每个操作 $2$ 输出一行一个整数。

Samples

4 6
1 2 3 8
2 1 4
1 2 -1
2 1 3
1 1 -2
1 2 -3
2 1 2

16
6
998244351