동적 수열 자료 구조

시간 제한

1초

메모리 제한

128 MB

정수 수열에 다음 네 가지 연산을 차례대로 수행한다. 위치는 현재 수열을 기준으로 1번부터 센다.

형식	설명
`1 A B X`	A번째부터 B번째까지의 모든 수를 X로 바꾼다.
`2 A B X`	A번째 수에는 X, A+1번째 수에는 2X, ..., B번째 수에는 (B-A+1)X를 더한다.
`3 C X`	C번째 수 바로 앞에 X를 삽입한다. C가 현재 수열의 크기+1이면 맨 뒤에 삽입한다.
`4 A B`	A번째 수부터 B번째 수까지의 합을 출력한다.

초기 수열과 수행할 연산들이 주어질 때, 4번 연산이 나올 때마다 그 결과를 출력하는 프로그램을 작성하시오.

첫째 줄에 N과 Q가 주어진다. N은 초기 수열의 크기이고, Q는 수행할 연산의 개수이다. (1 <= N, Q <= 100,000)

둘째 줄에는 초기 수열의 원소 N개가 공백으로 구분되어 주어진다. 각 원소는 100,000을 넘지 않는 음이 아닌 정수이다.

다음 Q개 줄에는 수행할 연산이 차례대로 주어진다. X가 있는 연산에서는 0 <= X <= 100이다. 구간 연산에서는 1 <= A <= B <= 현재 수열의 크기이고, 삽입 연산에서는 1 <= C <= 현재 수열의 크기+1이다.

4번 연산이 주어질 때마다 해당 구간의 합을 한 줄에 하나씩 출력한다. 합은 32비트 정수 범위를 넘을 수 있다.