줌

길이가 짝수인 수열 $A$가 주어진다. 처음에 $A$의 모든 원소는 $0$이다. 다음 쿼리를 처리하라.

• 1 l r b: $A_l, A_{l+1}, \cdots, A_r$에 각각 $b$를 더한다.
• 2 l: $1$ 이상 $N$ 이하의 모든 정수 $i$에 대해 $A_i$를 $A_{l+\lfloor \frac{i-1}{2} \rfloor}$로 바꾼다. 모든 $i$에 대한 교체는 동시에 이루어진다.
• 3: 지금까지 실행한 모든 1번, 2번 쿼리를 같은 순서로 다시 실행한다. 3번 쿼리가 실행한 1번, 2번 쿼리도 포함한다.
• 4 l r: $\sum_{i=l}^r A_i$를 $998\,244\,353$으로 나눈 나머지를 출력한다.

첫 번째 줄에 수열의 길이 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $Q$개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

4번 쿼리마다 그 답을 한 줄에 하나씩 출력한다.

• $2 \leq N \leq 100\,000$, $N$은 짝수이다.
• $1 \leq Q \leq 100\,000$
• 모든 1번 쿼리에 대해 $1 \leq l \leq r \leq N$, $1 \leq b \leq 998\,244\,352$이다.
• 모든 2번 쿼리에 대해 $1 \leq l \leq \frac{N}{2}+1$이다.
• 모든 4번 쿼리에 대해 $1 \leq l \leq r \leq N$이다.
• 입력에는 4번 쿼리가 적어도 하나 있다.
• 주어지는 모든 수는 정수이다.