Ο Παντελής πρόκειται να παντρευτεί! Έχει ράψει ένα μοδάτο κουστούμι, έχει βρει την εκκλησία και έχει στείλει και τα προσκλητήρια. Μοναδικό πρόβλημα είναι ότι δεν έχει βρει ακόμα τη νύφη!

Ολόκληρο το χωριό είναι στο πόδι. Όλες οι υποψήφιες νύφες στέκονται στη γραμμή, φορώντας τα νυφικά τους, για να μπορέσει ο Παντελής να διαλέξει τη μέλλουσα σύζυγό του. Οι νύφες είναι αριθμημένες από το 1 μέχρι το Ν και κάθε νύφη έχει ένα συγκεκριμένο βαθμό ελκυστικότητας Εi. Αν ισχύει ότι Ei>=Ej τότε η νύφη i δεν μπορεί να είναι λιγότερο ελκυστική από τη νύφη j. Όλες οι νύφες επιθυμούν διακαώς να παντρευτούν τον Παντελή, το θέμα είναι να θέλει κι αυτός.

Ο Παντελής αντιλαμβάνεται ότι έχει δύσκολο έργο έτσι αποφασίζει να κάνει αρκετά περάσματα ώστε να βρει την κατάλληλη. Κάθε ένα από τα περάσματα που κάνει ο Παντελής περιγράφεται από δύο ακεραίους L και R. Αν 1<=L<=R, τότε ο Παντελής ελέγχει διεξοδικά τις υποψήφιες που βρίσκονται στις θέσεις L, L+1,...,R-1,R, αλλιώς, αν 1<=R<=L, τότε ελέγχει τις υποψήφιες σε αντίστροφη σειρά R,R+1,...,L-1,L. Κάθε φορά που αντικρίζει μια υποψήφια νύφη, ο Παντελής ενθουσιάζεται μόνο αν ο βαθμός ελκυστικότητάς της είναι μεγαλύτερος ή ίσος από το μέγιστο βαθμό ελκυστικότητας των υπόλοιπων υποψηφίων, που αντίκρισε στο ίδιο πέρασμα. Σύμφωνα με την πιο πάνω διαδικασία, ο Παντελής πάντα ενθουσιάζεται μόλις αντικρίσει την πρώτη νύφη σε κάθε πέρασμα.

Για παράδειγμα, αν Ε = A=[4,2,6,4,6], L=1 και R=5, τότε ο Παντελής θα ενθουσιαστεί μόλις αντικρίσει τις νύφες στις θέσεις 1, 3 και 5 δηλαδή τρεις συνολικά, ενώ αν L=5 και R=1, θα ενθουσιαστεί μόλις αντικρίσει τις νύφες στις θέσεις 5 και 3 δηλαδή δύο συνολικά.

Οι νύφες όμως δεν κάθονται με σταυρωμένα τα χέρια. Κάποιες χρησιμοποιούν ειδικά «βοηθήματα» (κοκκινάδια, κτένες, αρώματα, μακιγιάζ κλπ.) ώστε να αυξήσουν την ελκυστικότητά τους, κάποιες άλλες όμως, που το παρακάνουν με το μακιγιάζ, μπορεί να χάσουν πόντους από την ελκυστικότητά τους. Κάποιες φορές δηλαδή ο Παντελής θα ενημερωθεί ότι o βαθμός ελκυστικότητας των νυφών από τη θέση L μέχρι τη θέση R έχει αυξηθεί (ή μειωθεί) κατά ένα ακέραιο Z.

Βοηθήστε τον Παντελή να βρει πόσες φορές θα ενθουσιαστεί σε κάθε ένα από τα περάσματά του.

Δεδομένα εισόδου

• Στην πρώτη γραμμή θα εμφανίζονται δύο ακέραιοι αριθμοί, το Ν και το Q. Το Ν αντιπροσωπεύει το πλήθος των υποψήφιων νυφών, ενώ το Q το πλήθος των ερωτημάτων που θα ακολουθήσουν.
• Στη δεύτερη γραμμή θα εμφανίζονται Ν ακέραιοι αριθμοί, Ε1, Ε2, Ε3…ΕΝ, ο βαθμός ελκυστικότητας κάθε μιας από τις νύφες.
• Στις επόμενες Q γραμμές θα εμφανίζονται ερωτήματα δύο τύπων. Πρώτου τύπου είναι τα ερωτήματα που ξεκινούν με τον αριθμό 1 και δευτέρου τύπου είναι τα ερωτήματα που ξεκινούν με τον αριθμό 2. Θα είναι της μορφής:

o 1 L R : Κάνε ένα πέρασμα από τη νύφη L μέχρι τη νύφη R, συμπεριλαμβανομένων, και βρες πόσες φορές θα ενθουσιαστεί ο Παντελής κατά τη διάρκεια του συγκεκριμένου περάσματος.

o 2 L R Z : Να αυξήσεις (ή να μειώσεις) το βαθμό ελκυστικότητας όλων των νυφών από τη θέση L μέχρι τη θέση R, συμπεριλαμβανομένων, κατά ένα ακέραιο Z.

Δεδομένα εξόδου

Για κάθε ένα από τα ερωτήματα πρώτου τύπου (που ξεκινούν με τον αριθμό 1), να εμφανίζεται σε ξεχωριστή γραμμή, ένας ακέραιος, το πλήθος των φορών που θα ενθουσιαστεί ο Παντελής κατά τη διάρκεια αυτού του περάσματος.