去年在河内参加 ICPC 亚太锦标赛时，你了解到了著名的汉诺塔问题。在该问题中，有三根杆子和若干个半径各不相同的圆盘，圆盘可以滑入任何一根杆子。杆子编号为 1 到 3。在任何时刻，每个圆盘都必须堆叠在其中一根杆子上，且每根杆子上的圆盘必须按半径从上到下递增的顺序排列。在一步操作中，你可以将一根杆子顶部的圆盘移动到另一根杆子的顶部，前提是该移动不违反上述限制。目标是以最少的步数将所有圆盘移动到杆子 1 上。
你现在正在解决这个著名问题的扩展版本。你有一个包含 $n$ 个整数的序列 $p_1, p_2, \dots, p_n$，其初始值已知。
你还需要处理 $q$ 个操作。每个操作属于以下两种类型之一：
修改操作：给定两个整数 $x$ 和 $y$。该操作要求你将 $p_x$ 的值修改为 $y$。
求解操作：给定两个整数 $l$ 和 $r$。该操作要求你解决一个汉诺塔问题，其中包含半径为 $l, l + 1, \dots, r$ 的 $r - l + 1$ 个圆盘，对于每个 $l \le i \le r$，半径为 $i$ 的圆盘初始堆叠在杆子 $p_i$ 上。每根杆子上初始堆叠的圆盘顺序满足前述限制。你需要求出将所有圆盘移动到杆子 1 所需的最少步数，结果对 998 244 353 取模。
你的任务是按顺序执行所有给定的操作。
输入格式
第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 100\,000$; $1 \le q \le 100\,000$)。第二行包含 $n$ 个整数，表示 $p_1, p_2, \dots, p_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$ 执行求解操作。
输入中至少包含一个求解操作。
输出格式
对于每个求解操作，按顺序输出将半径为 $l, l + 1, \dots, r$ 的圆盘移动到杆子 1 所需的最少步数，结果对 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
说明
样例输入/输出 #1 的解释：
第一个操作要求解决半径为 2、3 和 4 的圆盘初始分别堆叠在杆子 3、1 和 3 上的汉诺塔问题。如图 D.1 所示，所有圆盘可以在 6 步内移动到杆子 1。
图 D.1：将所有圆盘移动到杆子 1 的 6 个步骤。阴影杆表示最后一步移动的杆子。
第二个操作要求解决半径为 1、2 和 3 的圆盘初始分别堆叠在杆子 2、3 和 1 上的汉诺塔问题。
第四个操作要求解决半径为 2、3 和 4 的圆盘初始分别堆叠在杆子 3、3 和 3 上的汉诺塔问题。