Voda

Στην αυλή του, ο Marko έχει κατασκευάσει ένα ιστόγραμμα από ξύλινες στήλες: υπάρχουν ~n~ στήλες πλάτους ~1~, τοποθετημένες η μία δίπλα στην άλλη, και η στήλη στη θέση ~i~ έχει ύψος ~h_i~. Στον Marko αρέσει να αλλάζει την κατασκευή του, οπότε μερικές φορές αυξάνει, μειώνει ή αντικαθιστά το ύψος ορισμένων στηλών.

Μερικές φορές, ο Marko εξετάζει μόνο ένα τμήμα του ιστογράμματος, δηλαδή τις στήλες στις θέσεις από ~l~ έως ~r~, και φαντάζεται ότι πέφτει πάνω τους πολλή βροχή. Οι στήλες έξω από το εξεταζόμενο τμήμα δεν υπάρχουν εκείνη τη στιγμή, επομένως το νερό μπορεί να διαφύγει από την αριστερή πλευρά της στήλης ~l~ και από τη δεξιά πλευρά της στήλης ~r~. Η βροχή συνεχίζεται μέχρι να γεμίσει το ιστόγραμμα με νερό: το νερό παραμένει όπου παγιδεύεται ανάμεσα σε ψηλότερες στήλες και από τις δύο πλευρές, ενώ όλο το υπόλοιπο νερό διαφεύγει.

Ένα κελί διαστάσεων ~1 \times 1~ γεμάτο με νερό αντιστοιχεί σε μία μονάδα νερού.

Λέμε ότι μια στήλη είναι εντελώς βυθισμένη στο νερό αν υπάρχει νερό πάνω από την κορυφή της. Μια στήλη δεν είναι εντελώς βυθισμένη στο νερό αν η κορυφή της είναι στεγνή, δηλαδή δεν υπάρχει νερό πάνω από αυτήν. Το νερό μπορεί, ωστόσο, να αγγίζει μια τέτοια στήλη από το πλάι, μέχρι το ύψος της κορυφής της.

Ο Marko θα πραγματοποιήσει ~q~ ενέργειες με τη σειρά, καθεμία από τις οποίες είναι ενός από τους ακόλουθους πέντε τύπους:

• ~1~ ~i~ ~x~ - το ύψος της στήλης ~i~ γίνεται ~x~.
• ~2~ ~l~ ~r~ ~x~ - τα ύψη όλων των στηλών από τη θέση ~l~ έως τη θέση ~r~ γίνονται ~x~.
• ~3~ ~l~ ~r~ ~x~ - τα ύψη όλων των στηλών από τη θέση ~l~ έως τη θέση ~r~ αυξάνονται κατά ~x~ (ο αριθμός ~x~ μπορεί να είναι και αρνητικός).
• ~4~ ~l~ ~r~ - ο Marko εξετάζει τις στήλες από τη θέση ~l~ έως τη θέση ~r~ και θέλει να μάθει πόσες από αυτές δεν είναι εντελώς βυθισμένες στο νερό.
• ~5~ ~l~ ~r~ - ο Marko εξετάζει τις στήλες από τη θέση ~l~ έως τη θέση ~r~ και θέλει να μάθει πόσες μονάδες νερού συνολικά συγκρατούνται.

Βοηθήστε τον Marko και απαντήστε σε όλες τις ερωτήσεις του. Η εξέταση του ιστογράμματος δεν το μεταβάλλει, και το νερό εξαφανίζεται μετά από κάθε ερώτηση.

Είσοδος

Η πρώτη γραμμή θα περιέχει δύο θετικούς ακέραιους ~n~ και ~q~ (~1 \le n, q \le 200.000~), τον αριθμό των στηλών και τον αριθμό των ενεργειών.

Η δεύτερη γραμμή θα περιέχει ~n~ ακέραιους ~h_1,\ h_2,\ ...,\ h_n~ (~0 \le h_i \le 10^9~), τα αρχικά ύψη των στηλών.

Καθεμία από τις επόμενες ~q~ γραμμές θα περιέχει την περιγραφή μίας ενέργειας, σε μία από τις μορφές που δίνονται παραπάνω.

Ισχύει ότι ~1 \le i \le n~ και ~1 \le l \le r \le n~. Στις ενέργειες τύπου ~1~ και ~2~, ισχύει ~0 \le x \le 10^9~, ενώ στις ενέργειες τύπου ~3~ ισχύει ~-10^9 \le x \le 10^9~.

Είναι εγγυημένο ότι τα ύψη όλων των στηλών είναι ακέραιοι αριθμοί μεταξύ ~0~ και ~10^9~ σε κάθε χρονική στιγμή.

Έξοδος

Για κάθε ενέργεια τύπου ~4~ ή ~5~, με τη σειρά που εμφανίζεται, εκτυπώστε σε ξεχωριστή γραμμή την απάντηση στην αντίστοιχη ερώτηση του Marko.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~21~	~n, q \le 5000~.
~2~	~16~	Υπάρχουν μόνο ενέργειες τύπου ~4~.
~3~	~11~	Υπάρχουν μόνο ενέργειες τύπου ~4~ και ~5~.
~4~	~13~	Υπάρχουν μόνο ενέργειες τύπου ~1~ και ~4~.
~5~	~14~	Υπάρχουν μόνο ενέργειες τύπου ~1~, ~4~ και ~5~.
~6~	~16~	Υπάρχουν μόνο ενέργειες τύπου ~1~, ~2~, ~3~ και ~4~.
~7~	~19~	Δεν υπάρχουν πρόσθετοι περιορισμοί.

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

input

8 6
3 0 2 4 1 4 0 2
4 1 8
4 2 5
4 3 3
4 5 8
4 1 4
4 2 7

output

4
4
1
3
2
5

Επεξήγηση του πρώτου παραδείγματος

Το ιστόγραμμα είναι ~[3,\ 0,\ 2,\ 4,\ 1,\ 4,\ 0,\ 2]~. Στην πρώτη ερώτηση, ο Marko εξετάζει ολόκληρο το ιστόγραμμα. Το νερό συγκρατείται πάνω από τις στήλες ~2~, ~3~, ~5~ και ~7~ (~3~, ~1~, ~3~ και ~2~ μονάδες, αντίστοιχα), ενώ οι κορυφές των στηλών ~1~, ~4~, ~6~ και ~8~ παραμένουν στεγνές. Αυτές οι τέσσερις στήλες δεν είναι εντελώς βυθισμένες στο νερό, επομένως η απάντηση είναι ~4~.

Στη δεύτερη ερώτηση, ο Marko εξετάζει τις στήλες ~[0,\ 2,\ 4,\ 1]~. Τα ύψη πρώτα αυξάνονται και στη συνέχεια μειώνονται, επομένως όλο το νερό διαφεύγει είτε από την αριστερή είτε από τη δεξιά πλευρά. Καμία στήλη δεν είναι εντελώς βυθισμένη στο νερό και η απάντηση είναι ~4~.

input

6 5
5 1 3 2 4 1
5 1 6
4 1 6
5 2 5
5 4 6
4 3 3

output

6
3
1
0
1

Επεξήγηση του δεύτερου παραδείγματος

Το ιστόγραμμα είναι ~[5,\ 1,\ 3,\ 2,\ 4,\ 1]~. Όταν ο Marko εξετάζει ολόκληρο το ιστόγραμμα, το νερό ανάμεσα στις στήλες ~1~ και ~5~ φτάνει μέχρι το ύψος ~4~, ενώ στα δεξιά της στήλης ~5~ όλο το νερό διαφεύγει. Έτσι, συγκρατούνται ~0~, ~3~, ~1~, ~2~, ~0~, ~0~ μονάδες νερού πάνω από τις στήλες, δηλαδή συνολικά ~6~ μονάδες. Οι στήλες ~2~, ~3~ και 4 είναι εντελώς βυθισμένες στο νερό, ενώ οι υπόλοιπες τρεις δεν είναι. Επομένως, η απάντηση στη δεύτερη ερώτηση είναι ~3~.

input

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

output

5
2
1
0
5