수열

Yuta에게 $n$개의 정수로 이루어진 배열 $A_1, A_2, \ldots, A_n$이 있다. Yuta는 배열 $A$의 초기 내용을 $A'$에 복사해 보관한다. 처음에는 $A'_i = A_i$이다. 그 뒤 Yuta는 배열 $A$에 대해 $m$개의 연산을 차례로 수행한다.

연산은 세 종류가 있다.

• 1 l r: $l$ 이상 $r$ 이하인 모든 $i$에 대해 $A_i$의 합을 구한다.
• 2 l r k: 배열 $A$에 다음 코드를 그대로 실행한다. for (int i = l; i <= r; i++) A[i] = A[i - k];
• 3 l r: $l$ 이상 $r$ 이하인 모든 $i$에 대해 $A_i$를 $A'_i$의 값으로 되돌린다.

첫째 줄에 $n$과 $m$이 주어진다. ($1 \leq n, m \leq 2 \cdot 10^5$)

둘째 줄에 정수 $A_1, \ldots, A_n$이 주어진다. ($0 \leq A_i \leq 10^9$)

이후 $m$개의 줄에 연산이 한 줄씩 주어진다. 모든 연산은 $1 \leq l \leq r \leq n$과 $1 \leq k < l$을 만족한다.

종류가 1인 연산마다 구한 합을 한 줄에 출력한다.