Upit

Ο Mirko βαρέθηκε να εφαρμόζει κάθε είδους δομές δεδομένων για διαφορετικές εργασίες. Έτσι, αποφάσισε να βρει την απόλυτη δομή, αυτή που θα του επιτρέψει να χειριστεί την αγαπημένη του ακολουθία αριθμών. Βοήθησέ τον!

Ο Mirko θα σας δώσει την ακολουθία αριθμών του και μια ακολουθία ερωτημάτων που πρέπει να εκτελέσετε. Κάθε ερώτημα είτε ζητά πληροφορίες, είτε τροποποιεί την υπάρχουσα ακολουθία. Οι πιθανοί τύποι ερωτημάτων παρατίθενται παρακάτω.

Τύπος Ερωτήματος	Περιγραφη	Παράδειγμα
1 A B X	Ορίστε όλα τα στοιχεία από ~A~-οστό έως ~B~-οστό (συμπεριλαμβανομένων αυτών) στην τιμή ~X~	~(9,\;8,\;7,\;6,\;5,\;4,\;3,\;2,\;1) \rightarrow 1 3 5 0 \rightarrow (9,\;8, \textbf{ 0, 0, 0},\;4,\;3,\;2,\;1)~
2 A B X	Προσθέστε ~X~ στο ~A~-οστό στοιχείο, ~2 \times X~ στο~(A+1)~-οστό,~\ldots\;~, και ~(B-A+1) \times X~ στο ~B~-οστό στοιχείο	~(9,\;8,\;7,\;6,\;5,\;4,\;3,\;2,\;1) \rightarrow 2 3 5 2 \rightarrow (9,\;8, \textbf{9, 10, 11},\;4,\;3,\;2,\;1)~
3 C X	Εισαγάγετε νέο στοιχείο με τιμή ~X~ αμέσως πριν από το ~C~-οστό στοιχείο	~(9,\;8,\;7,\;6,\;5,\;4,\;3,\;2,\;1) \rightarrow 3 4 100 \rightarrow (9,\;8,\;7, \textbf{100},\;6,\;5,\;4,\;3\;,\;2,\;1)~
4 A B	Βρείτε το άθροισμα όλων των στοιχείων από ~A~-οστό έως ~B~-οστό	~(2,\;18,\;7,\;6,\;1, \textbf{4, 7},\;7,\;2) \rightarrow 4 6 7 \rightarrow\; ~αποτέλεσμα: ~11~

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N~ και ~Q\;(1 \leq N,\;Q \leq 100\,000)~, το μήκος της αρχικής ακολουθίας και τον αριθμό των ερωτημάτων.

Η ακόλουθη γραμμή περιέχει την αρχική σειρά. Η ακολουθία αποτελείται από μη αρνητικούς ακέραιους όχι μεγαλύτερους από ~100000~ που χωρίζονται από ένα μόνο διάστημα.

Οι ακόλουθες ~Q~ γραμμές περιέχουν ερωτήματα με τη μορφή που περιγράφεται παραπάνω. Σε όλα τα ερωτήματα, ~1 \leq X \leq 100,\;1 \leq A \leq B \leq~ currentSequenceLength και ~1 \leq C \leq currentSequenceLength+1~.

Έξοδος

Για κάθε ερώτημα τύπου 4, τυπώστε μια γραμμή που περιέχει το ζητούμενο άθροισμα.

Σημείωση: παρατηρήστε ότι ορισμένα αθροίσματα δεν χωρούν σε ακέραιο τύπο δεδομένων 32-bit.

Παραδείγματα

input

5 5
1 2 3 4 5
1 5 5 0
4 4 5
4 5 5
2 1 5 1
4 1 5

output

4
0
25

input

1 7
100
3 1 17
3 2 27
3 4 37
4 1 1
4 2 2
4 3 3
4 4 4

output

17
27
100
37