Aladin

Ο Aladin περπατούσε στο μονοπάτι μια μέρα, όταν βρήκε το πιο περίεργο πράγμα. ~N~ άδεια κουτιά ακριβώς δίπλα σε μια παράξενη μηχανή εξωγήινων. Μετά από λίγο ψάξιμο έβαλε τη μηχανή να κάνει κάτι. Το μηχάνημα δέχεται πλέον ~4~ ακέραιους αριθμούς ~L,\;R,\;A~ και ~B~. Μετά από αυτό, πατώντας το μεγάλο κόκκινο λαμπερό κουμπί με την ένδειξη "NEDIRAJ" το μηχάνημα θα τρελαθεί και θα ακολουθήσει την επόμενη διδικασία:

• Ορίστε τον αριθμό των πετρωμάτων στο κουτί με την ένδειξη ~L~ σε ~A~ modulo ~B~.
• Προχωρά για να πετάξει στο κουτί με την ένδειξη ~L+1~ και ορίζει τον αριθμό των πετρωμάτων εκεί σε ~(2 \cdot A)~ mod ~B~.
• Προχωρά για να πετάξει στο κουτί με την ένδειξη ~L+2~ και να ορίσει τον αριθμό των πετρωμάτων εκεί σε ~(3 \cdot A)~ mod ~B~.
• Γενικά, επισκέπτεται κάθε κουτί με ετικέτα μεταξύ ~L~ και ~R~ και ορίζει τον αριθμό των πετρωμάτων εκεί σε ~((X - L + 1) \cdot A)~ mod ~B~. όπου ~X~ είναι η ετικέτα του κουτιού.
• Έπειτα επισκέπτεται το κουτί με το γράμμα ~R~. Ηρεμεί (τελειώνει την δουλειά) και προχωρά σε περισσότερες οδηγίες.

Κατά τη διάρκεια του παιχνιδιού ο Aladin αναρωτιέται ποιος είναι ο συνολικός αριθμός των πετρωμάτων σε κάποια σειρά κουτιών.
Γράψτε ένα πρόγραμμα που προσομοιώνει τη συσκευή και απαντά στις ερωτήσεις του Aladin.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~N~ και ~Q\;(1 \le N \le 1\,000\,000\,000,\;1 \le Q \le 50\,000)~, τον αριθμό πλαισίων και τον αριθμό ερωτημάτων.
Οι επόμενες ~Q~ γραμμές περιέχουν πληροφορίες για την προσομοίωση.
Εάν η γραμμή ξεκινά με ~1~, τότε ακολουθεί τη μορφή "~1\;L\;R\;A\;B~" ~(1 \le L \le R \le N,\;1 \le A, B \le 1\,000\,000)~, που σημαίνει ότι ο Aladin πληκτρολογεί τους αριθμούς ~L,\;R\;A~ και ~B~ στη συσκευή και επέτρεψε στη συσκευή να κάνει τη δουλειά της.
Εάν η γραμμή ξεκινά με ~2~, τότε ακολουθεί τη μορφή "~2\;L\;R~" ~(1 \le L \le R \le N)~.
Αυτό σημαίνει ότι ο Aladin αναρωτιέται πόσα πετρώματα είναι συνολικά αυτά που υπάρχουν σε κουτιά με την ένδειξη ~L~ έως ~R~ (~[L,\;R]~).

Έξοδος

Για κάθε ερώτημα που ξεκινά με ~2~ τυπώνετε την απάντηση στο συγκεκριμένο ερώτημα.
Τα ερωτήματα πρέπει να υποβάλλονται σε επεξεργασία με τη σειρά που δίνονται στην είσοδο.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~30~% των συνολικών πόντων θα ισχύει ~N~ και ~Q \le 1000~. Σε δοκιμαστικές περιπτώσεις αξίας ~70~% των συνολικών πόντων θα ισχύει ~Q \le 1000~.

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

input

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

output

0
3

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

Τα πλαίσια αρχικά περιέχουν ~{0, 0, 0, 0, 0, 0}~, ~0~ πετρώματα συνολικά.
Μετά από αυτό, η συσκευή ορίζει τα πετρώματα σε ~\{1 mod 2,\;2 mod 2,\;3 mod 2,\;4 mod 2,\;5 mod 2,\;0\}\;=\;\{1,\;0,\;1,\;0,\;1,\;0\}~ ή ~3~ πετρώματα συνολικά.

input

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

output

3
2
1
0

input

4 4
1 1 4 7 9
2 1 4
1 1 4 1 1
2 1 4

output

16
0