Garaža

Τον τελευταίο καιρό, ο Slavko μελετά ακολουθίες φυσικών αριθμών. Βρίσκει ενδιαφέρουσα μια ακολουθία αν ο μεγαλύτερος κοινός διαιρέτης όλων των στοιχείων της ακολουθίας είναι μεγαλύτερος από 1.

Χθες, βρήκε μια ακολουθία που αποτελείται από ~N~ φυσικούς αριθμούς στο γκαράζ του. Επειδή βαριόταν πραγματικά, αποφάσισε να απασχοληθεί κάνοντας απλές ερωτήσεις. Κάθε ερώτημα μπορεί να είναι ενός από τους δύο τύπους:

1. Αλλάξτε την τιμή στη θέση ~X~, στην ακολουθία, σε ~V~.
2. Προσδιορίστε τον αριθμό των συνεχόμενων υπακολουθιών με ενδιαφέρον, που περιέχονται στο διάστημα ~[L,\;R]~ της ακολουθίας.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους αριθμούς ~N~ και ~Q\;(1 \le N, Q \le 10^5)~, που αντιπροσωπεύει τον αριθμό​ των στοιχείων στην ακολουθία και τον αριθμό των ερωτημάτων, αντίστοιχα.
Η ακόλουθη γραμμή περιέχει ~N~ φυσικούς αριθμούς ~A_i\;(1 \le A_i \le 10^9)~ που αντιπροσωπεύουν τους αριθμούς στην αρχική ακολουθία.
Κάθε μία από τις ακόλουθες γραμμές ~Q~ περιέχει ένα ερώτημα της ακόλουθης φόρμας:

• Ο πρώτος αριθμός στη γραμμή μπορεί να είναι 1 ή 2 και αντιπροσωπεύει τον τύπο της ερώτηση.
• Εάν το ερώτημα είναι τύπου 1, ακολουθούν δύο αριθμοί, ~X\;(1 \le X \le N)~ και ~V~ ~(1 \le V \le 10^9)~ από την εργασία.
• Εάν το ερώτημα είναι τύπου 2, ακολουθούν δύο αριθμοί, ~L~ και ~R~ ~(1 \le L \le R \le N)~ που αντιπροσωπεύουν το αριστερό και δεξιό όριο διαστήματος.

Έξοδος

Για κάθε ερώτημα τύπου 2, τυπώστε τον αριθμό των συνεχόμενων υπακολουθιών που έχουν ενδιαφέρον.

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

input

5 1
8 4 3 9 1
2 2 5

output

4

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

Το διάστημα από τη 2^η έως την 5^η θέση αποτελείται από αριθμούς ~(4,\;3,\;9,\;1)~. Σε αυτό, είναι τα ακόλουθα ενδιαφέρουσες συνεχόμενες υποσειρές (σημειώνονται με τετράγωνες αγκύλες):
[4] ~3\;9\;1~,   ~4~ [3] ~9\;1~,   ~4\;3~ [9] ~1~,   ~4~ [3 9] ~1~

input

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

output

6
1

input

4 3
2 2 2 2
2 1 4
1 2 3
2 1 4

output

10
5