31036번 - 줌

길이가 짝수 $N$인 수열 $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 \le l \le r \le N$, $1 \le b \le 998\,244\,352$
• 모든 2번 종류의 쿼리에 대해서 $1 \le l \le \frac{N}{2}+1$
• 모든 4번 종류의 쿼리에 대해서 $1 \le l \le r \le N$
• 입력에는 적어도 하나의 4번 종류의 쿼리가 존재한다.
• 주어지는 모든 수는 정수이다.