Vera and Modern Art

Αφού εμπνεύστηκε από τον μεγάλο ζωγράφο Picowso, η Vera αποφάσισε να φτιάξει το δικό της αριστούργημα. Έχει μια άδεια επιφάνεια ζωγραφικής που μπορεί να μοντελοποιηθεί ως ένα 2D άπειρο επίπεδο συντεταγμένων. Στη Vera αρέσουν οι δυνάμεις του δύο (~1~, ~2~, ~4~, ~8~, ~16~, . . .) και θα ζωγραφίσει μερικά σημεία με επαναλαμβανόμενο τρόπο χρησιμοποιώντας το μεγέθη βήματος που είναι δύναμη του δύο.

Η Vera θα ζωγραφίσει ~N~ φορές. Η ~i~-οστη φορά μπορεί να περιγραφεί με τρεις ακέραιους ~x_i~, ~y_i~, ~v_i~. Έστω ότι το ~a_i~ είναι η μεγαλύτερη δύναμη του δύο όχι μεγαλύτερη από ~x_i~ και έστω ότι ~b_i~ είναι η μεγαλύτερη δύναμη του δύο όχι μεγαλύτερη από ~y_i~. Η Vera θα προσθέσει μια σταγόνα χρώματος με χρώμα ~v_i~ σε όλα τα σημεία που είναι της μορφής (~x_i + a_{i}p, y_i + b_{i}q~), όπου τα ~p~, ~q~ είναι μη αρνητικοί ακέραιοι αριθμοί. Ένα σημείο μπορεί να έχει πολλές σταγόνες χρώματος πάνω του ή να έχει πολλές σταγόνες του ίδιου χρώματος.

Στη συνέχεια η Vera θα κάνει ~Q~ ερωτήσεις. Για την ~j~-οστη ερώτηση θέλει να μάθει το χρώμα στο σημείο (~r_j~ , ~c_j~). Το χρώμα σε ένα σημείο είναι ίσο με το άθροισμα των χρωμάτων όλων των σταγόνων χρώματος σε αυτό το σημείο. Αν Δεν υπάρχουν σταγόνες χρώματος σε ένα σημείο, το χρώμα αυτού του σημείου είναι ~0~.

Εφόσον είστε αναγκασμένοι να γίνετε βοηθός τέχνης της, θα πρέπει να απαντήσετε στις ερωτήσεις της Vera.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~N~, ~Q~, χωρισμένους με ένα κενό (~1 \le N, Q \le 2 \cdot 10^5~).

Οι επόμενες ~N~ γραμμές καθεμία περιέχουν τρεις, χωρισμένους με κενό, ακέραιους ~x_i~, ~y_i~, ~v_i~ που αντιπροσωπεύουν τις σταγόνες χρώματος του χρώματος ~v_i~ (~1 \le i \le N~, ~1 \le v_i \le 10\,000~, ~1 \le x_i, y_i \le 10^{18}~).

Οι επόμενες ~Q~ γραμμές καθεμία περιέχουν δύο, χωρισμένους με κενό, ακέραιους ~r_j~, ~c_j~, που αντιπροσωπεύουν τις ~Q~ ερωτήσεις σχετικά με το σημείο (~r_j~, ~c_j~) (~1 \le j \le Q~, ~1 \le r_j \le 10^{18}~, ~1 \le c_j \le 10^{18}~).

Βαθμολογία

Για ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~N, Q \le 2\,000~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~y_i = 1~ (~1 \le i \le N~).

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~N, Q \le 10^5~ και ~1 \le r_j, c_j \le 10^9~ (~1 \le j \le Q~).

Έξοδος

Η έξοδος θα έχει ~Q~ γραμμές. Η ~j~-οστη γραμμή (~1 \le j \le Q~) θα πρέπει να έχει έναν ακέραιο, ο οποίος θα είναι το χρώμα του σημείου (~r_j~, ~c_j~).

Παράδειγμα

input

5 6
1 2 1
3 4 2
4 5 3
6 3 4
7 1 5 
2 6
7 8
5 9
11 2
10 7
4 5

output

1
8
0
6
4
3

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

Έστω ότι τα χρώματα ~1~, ~2~, ~3~, ~4~, ~5~ είναι κόκκινο, μπλε, πράσινο, πορτοκαλί και μωβ αντίστοιχα.

Έστω ότι ~p~, ~q~ είναι μη αρνητικοί ακέραιοι, τότε:

• Τα σημεία (~1 + p~, ~2 + 2q~) έχουν μία κόκκινη σταγόνα χρώματος.
• Τα σημεία (~3 + 2p~, ~4 + 4q~) έχουν μία μπλε σταγόνα χρώματος.
• Τα σημεία (~4 + 4p~, ~5 + 4q~) έχουν μία πράσινη σταγόνα χρώματος.
• Τα σημεία (~6 + 4p~, ~3 + 2q~) έχουν μία πορτοκαλί σταγόνα χρώματος.
• Τα σημεία (~7 + 4p~, ~1 + q~) έχουν μία μωβ σταγόνα χρώματος.

Ο πίνακας από το (~0~, ~0~) έως το (~11~, ~11~) φαίνεται παρακάτω: Μπορούμε να δούμε ότι:

• το (~2~, ~6~) έχει μία κόκκινη σταγόνα χρώματος, οπότε έχει χρώμα ~1~.
• το (~7~, ~8~) έχει μία κόκκινη, μπλε και μωβ σταγόνα χρώματος, οπότε έχει χρώμα ~1 + 2 + 5 = 8~.
• το (~5~, ~9~) δεν έχει καθόλου σταγόνες χρώματος, οπότε έχει χρώμα ~0~.
• το (~11~, ~2~) έχει μία κόκκινη και μωβ σταγόνα χρώματος, οπότε έχει χρώμα ~1 + 5 = 6~.
• το (~10~, ~7~) έχει μία πορτοκαλί σταγόνα χρώματος, οπότε έχει χρώμα ~4~.

• το (~4~, ~5~) έχει μία πράσινη σταγόνα χρώματος, οπότε έχει χρώμα ~3~.