18379번 - 이메이미의 수쿼 노트

이메이미는 수열과 쿼리 문제를 풀다가 '로컬에서는 잘 나오는데 틀렸다고 함'이라는 결과를 받고 펜과 노트로 디버깅을 하는 중이다. 이메이미는 이미 노트에 길이 N의 초기 수열을 적어 두었고, 노트에 쿼리를 하나씩 추가하며 수열을 직접 계산하려고 한다. 하나의 쿼리는 [T, L, R, V] 4개의 수로 이루어져 있는데, T의 값은 연산의 종류를 뜻하며 아래와 같은 연산을 한다.

• T = 0 : 수열의 L번째 원소부터 R번째 원소까지 V를 더한다.
• T = 1 : 수열의 L번째 원소부터 R번째 원소까지 V를 곱한다.
• T = 2 : 수열의 L번째 원소부터 R번째 원소까지의 합을 출력한다.

그런데 지금까지의 쿼리를 잘못 적었다는 것을 깨달은 이메이미는 충격에 빠졌다. 지금까지의 쿼리를 모두 다시 적는 것은 힘든 일이기 때문에 이메이미는 지금까지의 쿼리를 수정하는 대신 지금까지의 쿼리를 수정하는 새로운 쿼리를 적는 것으로 대신하기로 했다. T = 3을 적은 것은 지금까지 쿼리의 T를 잘못 적었다는 의미이며, 지금까지 적은 쿼리 [T', L', R', V']가 사실 [(T' + V) mod 4, L', R', V']였다는 의미이다. 수정된 쿼리의 T'도 3일 경우 그 앞의 쿼리들은 여러 번 수정될 수도 있지만, 수정된 쿼리의 T'이 2일 경우에 그 값을 출력할 필요는 없다.

이메이미는 원소가 열 개가 넘는 수열을 계산하기가 힘들어서 고생하고 있다. 이메이미의 노트를 보고 대신 계산해주는 프로그램을 만들어주자.

1번째 줄에는 수열의 크기 N, 쿼리의 수 M이 공백으로 구분되어 주어진다.

2번째 줄에는 수열의 원소 A₁, A₂, ..., A_N이 공백으로 구분되어 주어진다.

i + 2번째 줄에는 i번째 쿼리 T_i, L_i, R_i, V_i가 공백으로 구분되어 주어진다. (1 ≤ i ≤ M)

T_i = 2인 쿼리가 주어질 때마다 쿼리의 답을 998,244,353으로 나눈 나머지를 한 줄에 하나씩 출력한다.

• 1 ≤ N, M ≤ 100,000
• 0 ≤ A_i < 998,244,353 (1 ≤ i ≤ N)
• 0 ≤ T_i ≤ 3 (1 ≤ i ≤ M)
• 1 ≤ L_i ≤ R_i ≤ N (1 ≤ i ≤ M)
• 0 ≤ V_i < 998,244,353 (1 ≤ i ≤ M)
• T_i = 2인 1 ≤ i ≤ M이 존재한다.

 문제를 엄밀하게 정의하기 위해 i번째로 들어온 쿼리를 Q_i = [T_i, L_i, R_i, V_i]라고 하자. 쿼리열 Q = [Q₁, Q₂, ..., Q_q]는 정의역과 공역이 길이 N의 수열인 함수로 정의되며, 아래와 같이 재귀적으로 정의할 수 있다.

• [](A) = A
• $(Q+[0, L, R, V])(A)[i] = \begin{cases} Q(A)[i] + V & \text{if }L\leq i\leq R \\ Q(A)[i] & \text{otherwise} \end{cases}$
• $(Q+[1, L, R, V])(A)[i] = \begin{cases} Q(A)[i] \times V & \text{if }L\leq i\leq R \\ Q(A)[i] & \text{otherwise} \end{cases}$
• Q + [2, L, R, V] = Q
• Q + [3, L, R, V] = [[(T₁ + V) mod 4, L₁, R₁, V₁], ..., [(T_q + V) mod 4, L_q, R_q, V_q]]

 T_i = 2인 모든 i에 대해 $\left(\sum\limits_{j=L_i}^{R_i}{[Q_1, Q_2, \cdots, Q_i](A)[j]}\right)\mod 998,244,353$를 출력하는 프로그램을 작성해야 한다.