Mirko got tired of implementing all kinds of data structures for different tasks, so he decided to come up with the ultimate structure, one that will allow him to manipulate his favourite number sequence. Help him!

Mirko will give you his number sequence and a sequence of queries you must execute. Each query either asks for information or modifies the existing sequence. The possible query types are:

• 1 A B X — set all elements from the \(A\)-th to the \(B\)-th (inclusive) to value \(X\).
  $$ (9, 8, 7, 6, 5, 4, 3, 2, 1) \;\xrightarrow{\;1\ 3\ 5\ 0\;}\; (9, 8, 0, 0, 0, 4, 3, 2, 1) $$
• 2 A B X — add \(X\) to the \(A\)-th element, \(2X\) to the \((A{+}1)\)-th, \(\ldots\), and \((B{-}A{+}1)\,X\) to the \(B\)-th element.
  $$ (9, 8, 7, 6, 5, 4, 3, 2, 1) \;\xrightarrow{\;2\ 3\ 5\ 2\;}\; (9, 8, 9, 10, 11, 4, 3, 2, 1) $$
• 3 C X — insert a new element with value \(X\) immediately before the \(C\)-th element.
  $$ (9, 8, 7, 6, 5, 4, 3, 2, 1) \;\xrightarrow{\;3\ 4\ 100\;}\; (9, 8, 7, 100, 6, 5, 4, 3, 2, 1) $$
• 4 A B — find the sum of all elements from the \(A\)-th to the \(B\)-th. For \((2, 18, 7, 6, 1, 4, 7, 7, 2)\), the query \(4\ 6\ 7\) gives \(4 + 7 = 11\).

The first line of input contains integers \(N\) and \(Q\) (\(1 \le N, Q \le 100\,000\)), the starting sequence length and the number of queries.

The following line contains the starting sequence. It consists of non-negative integers not greater than \(100\,000\) separated by a single space.

The following \(Q\) lines contain the queries in the format described above. In all queries, \(1 \le X \le 100\), \(1 \le A \le B \le \text{currentSequenceLength}\), and \(1 \le C \le \text{currentSequenceLength} + 1\).

For each query of type \(4\), output one line containing the requested sum.

Note: some sums won't fit into a \(32\)-bit integer data type.

riseoj 작성

출처 COCI 2010/2011 Contest 7