Al visitar Hanoi para competir en The ICPC Asia Pacific Championship el año pasado, conociste el famoso problema de la torre de Hanoi. Hay tres varillas y varios discos de radios distintos, que pueden deslizarse sobre cualquier varilla. Las varillas están numeradas de $1$ a $3$. En todo momento, cada disco debe estar apilado en una varilla, y los discos de cada varilla deben estar ordenados por radio creciente de arriba abajo. En un paso puedes mover el disco superior de una varilla a la parte superior de otra, siempre que no se viole la restricción anterior. El objetivo es mover todos los discos a la varilla $1$ con el mínimo número de pasos.
Resuelves una extensión de este famoso problema. Tienes una secuencia de $n$ enteros $p_1,p_2,\ldots,p_n$, cuyos valores iniciales se te dan.
También se dan $q$ operaciones. Cada operación es de uno de los siguientes tipos:
Operación de cambio: Se dan dos enteros $x$ e $y$. Debes cambiar el valor de $p_x$ a $y$.
Operación de resolución: Se dan dos enteros $l$ y $r$. Debes resolver la torre de Hanoi con $r-l+1$ discos de radios $l,l+1,\ldots,r$, donde el disco de radio $i$ está inicialmente en la varilla $p_i$ para cada $l \le i \le r$. El orden inicial de los discos de cada varilla satisface la restricción anterior. Debes hallar el mínimo número de pasos para mover todos los discos a la varilla $1$, módulo $998\,244\,353$.
Tu tarea es realizar todas las operaciones dadas en orden.
Entrada
La primera línea contiene dos enteros $n$ y $q$ ($1 \le n \le 100\,000$; $1 \le q \le 100\,000$). La segunda contiene $n$ enteros que representan los valores iniciales de $p_1,p_2,\ldots,p_n$ ($1 \le p_i \le 3$). Las siguientes $q$ líneas representan las operaciones en el orden de ejecución. Cada línea tiene uno de estos formatos:
c x y($1 \le x \le n$; $1 \le y \le 3$) para aplicar una operación de cambio con los enteros indicados $x$ e $y$.s l r($1 \le l \le r \le n$) para aplicar una operación de resolución con los enteros indicados $l$ y $r$.
La entrada contiene al menos una operación de resolución.
Salida
Para cada operación de resolución, en orden, imprime el mínimo número de pasos para resolver la torre de Hanoi con discos de radios $l,l+1,\ldots,r$, módulo $998\,244\,353$.
Ejemplos
Entrada 1
4 4 2 3 1 3 s 2 4 s 1 3 c 3 3 s 2 4
Salida 1
6 2 7
Nota
La primera operación exige resolver la torre de Hanoi con discos de radios $2$, $3$ y $4$ inicialmente en las varillas $3$, $1$ y $3$, respectivamente. Todos los discos pueden moverse a la varilla $1$ en 6 pasos, como muestra la figura D.1.
Figura D.1: 6 pasos para mover todos los discos a la varilla $1$. La varilla sombreada representa la varilla movida en el último paso.
La segunda operación exige resolver la torre de Hanoi con discos de radios $1$, $2$ y $3$ inicialmente en las varillas $2$, $3$ y $1$, respectivamente.
La cuarta operación exige resolver la torre de Hanoi con discos de radios $2$, $3$ y $4$ inicialmente en las varillas $3$, $3$ y $3$, respectivamente.