Podczas ubiegłorocznej wizyty w Hanoi na The ICPC Asia Pacific Championship poznałeś słynny problem Wieży Hanoi. W problemie są trzy pręty oraz kilka krążków o różnych promieniach, które można nasunąć na dowolny pręt. Pręty są ponumerowane od $1$ do $3$. W każdej chwili każdy krążek musi znajdować się na jednym z prętów, a krążki na każdym pręcie muszą być ułożone od góry do dołu w rosnącej kolejności promieni. W jednym kroku można przenieść górny krążek z jednego pręta na wierzch innego, o ile nie narusza to powyższego ograniczenia. Celem jest przeniesienie wszystkich krążków na pręt $1$ w najmniejszej liczbie kroków.

Rozwiązujesz rozszerzenie tego słynnego problemu. Masz ciąg $n$ liczb całkowitych $p_1,p_2,\ldots,p_n$, których początkowe wartości są dane.

Danych jest też $q$ operacji. Każda jest jednego z następujących rodzajów:

Operacja zmiany: Dane są dwie liczby całkowite $x$ i $y$. Należy zmienić wartość $p_x$ na $y$.

Operacja rozwiązania: Dane są dwie liczby całkowite $l$ i $r$. Należy rozwiązać Wieżę Hanoi z $r-l+1$ krążkami o promieniach $l,l+1,\ldots,r$, gdzie krążek o promieniu $i$ początkowo znajduje się na pręcie $p_i$ dla każdego $l \le i \le r$. Początkowa kolejność krążków na każdym pręcie spełnia wcześniej opisane ograniczenie. Należy znaleźć najmniejszą liczbę kroków potrzebnych do przeniesienia wszystkich krążków na pręt $1$, modulo $998\,244\,353$.

Twoim zadaniem jest wykonanie wszystkich danych operacji kolejno.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ i $q$ ($1 \le n \le 100\,000$; $1 \le q \le 100\,000$). Drugi zawiera $n$ liczb całkowitych, początkowe wartości $p_1,p_2,\ldots,p_n$ ($1 \le p_i \le 3$). Kolejne $q$ wierszy opisuje operacje w kolejności wykonywania. Każdy wiersz ma jeden z formatów:

1. c x y ($1 \le x \le n$; $1 \le y \le 3$) wykonuje operację zmiany dla wskazanych liczb $x$ i $y$.
2. s l r ($1 \le l \le r \le n$) wykonuje operację rozwiązania dla wskazanych liczb $l$ i $r$.

Wejście zawiera co najmniej jedną operację rozwiązania.

Wyjście

Dla każdej operacji rozwiązania, kolejno, wypisz najmniejszą liczbę kroków potrzebnych do rozwiązania Wieży Hanoi z krążkami o promieniach $l,l+1,\ldots,r$, modulo $998\,244\,353$.

Przykład

Wejście 1

4 4
2 3 1 3
s 2 4
s 1 3
c 3 3
s 2 4

Wyjście 1

6
2
7

Uwagi

Pierwsza operacja wymaga rozwiązania Wieży Hanoi z krążkami o promieniach $2$, $3$ i $4$ początkowo na prętach odpowiednio $3$, $1$ i $3$. Wszystkie krążki można przenieść na pręt $1$ w 6 krokach, jak na rysunku D.1.

Rysunek D.1: 6 kroków przenoszących wszystkie krążki na pręt $1$. Zacieniowany pręt oznacza pręt przemieszczony w ostatnim kroku.

Druga operacja wymaga rozwiązania Wieży Hanoi z krążkami o promieniach $1$, $2$ i $3$ początkowo na prętach odpowiednio $2$, $3$ i $1$.

Czwarta operacja wymaga rozwiązania Wieży Hanoi z krążkami o promieniach $2$, $3$ i $4$ początkowo na prętach odpowiednio $3$, $3$ i $3$.