Πρόβλημα

Υπάρχει μία ακολουθία ~\alpha~ μήκους ~n~. Εκφράζουμε το ~i~-οστό στοιχείο της ως ~\alpha_i~. Ζητάται η υλοποίηση 3 ερωτημάτων πάνω στην ακολουθία:

• 0 x y t: Για κάθε ~x \leq i \leq y~, θέτουμε ~\alpha_{i,new} = \min(\alpha_i, t)~
• 1 x y: Να εκτυπωθεί το ~\max_i \alpha_i~ για ~x \leq i \leq y~
• 2 x y: Να εκτυπωθεί το ~\sum_i \alpha_i~ για ~x \leq i \leq y~

Μορφή Εισόδου

Στην πρώτη γραμμή δίνεται ακέραιος ~T~, το πλήθος των περιπτώσεων ελέγχου.

Κάθε περίπτωση ελέγχου ξεκινάει με 2 ακεραίους ~n, m~ στην πρώτη γραμμή: το μήκος της ακολουθίας και το πλήθος των ερωτημάτων. Στην δεύτερη γραμμή έχουμε την ακολουθία (δλδ. ~n~ ακεραίους ~\alpha_1 \dots \alpha_n~). Ακολουθούν ~m~ γραμμές στην μορφή των ερωτημάτων που δώθηκαν παραπάνω.

Μορφή Εξόδου

Για κάθε ερώτημα τύπου 1 ή 2, να εκτυπώσετε την ζητούμενη τιμή.

Παράδειγμα

Είσοδος:

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

Έξοδος:

5
15
3
12

Περιορισμοί

• ~\sum n, \sum m \leq 1,000,000~
• ~\alpha_i, t < 2^{31}~
• ~1 \leq x,y \neq n~