작년에 The ICPC Asia Pacific Championship에 참가하기 위해 Hanoi를 방문했을 때, 유명한 하노이의 탑 문제를 알게 되었다. 이 문제에는 막대 3개와 반지름이 서로 다른 여러 원판이 있으며, 원판은 어느 막대에나 끼울 수 있다. 막대는 $1$부터 $3$까지 번호가 붙는다. 언제나 각 원판은 막대 하나에 쌓여 있어야 하며, 각 막대의 원판은 위에서 아래로 반지름이 증가하는 순서여야 한다. 한 단계에서는 위 조건을 위반하지 않는 한, 한 막대의 맨 위 원판을 다른 막대의 맨 위로 옮길 수 있다. 목표는 모든 원판을 최소 단계로 막대 $1$에 옮기는 것이다.
이 유명한 문제의 확장을 풀려고 한다. 정수 $n$개로 이루어진 수열 $p_1,p_2,\ldots,p_n$의 초깃값이 주어진다.
또한 $q$개의 연산이 주어진다. 각 연산은 다음 중 하나이다.
변경 연산: 두 정수 $x$, $y$가 주어진다. $p_x$의 값을 $y$로 바꾸어야 한다.
해결 연산: 두 정수 $l$, $r$이 주어진다. 반지름이 $l,l+1,\ldots,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$)가 주어진다. 둘째 줄에는 $p_1,p_2,\ldots,p_n$의 초깃값을 나타내는 정수 $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,\ldots,r$인 원판으로 하노이의 탑 문제를 해결하는 최소 단계 수를 $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
참고
첫 번째 연산에서는 반지름이 $2$, $3$, $4$인 원판이 각각 막대 $3$, $1$, $3$에 놓인 하노이의 탑 문제를 풀어야 한다. 그림 D.1과 같이 모든 원판을 막대 $1$로 6단계에 옮길 수 있다.
그림 D.1: 모든 원판을 막대 $1$로 옮기는 6단계. 음영으로 표시된 막대는 마지막 단계에서 이동한 막대를 나타낸다.
두 번째 연산에서는 반지름이 $1$, $2$, $3$인 원판이 각각 막대 $2$, $3$, $1$에 놓인 하노이의 탑 문제를 풀어야 한다.
네 번째 연산에서는 반지름이 $2$, $3$, $4$인 원판이 각각 막대 $3$, $3$, $3$에 놓인 하노이의 탑 문제를 풀어야 한다.