Triangle Collection

Η Αλίκη έχει μια συλλογή από κλαδιά. Αρχικά, έχει ~c_l~ κλαδιά μήκους ~l~ για κάθε ~l = 1, . . . , N~.

Η Αλίκη θα ήθελε να χρησιμοποιήσει τα κλαδιά για να φτιάξει μερικά ισοσκελή τρίγωνα. Ένα ισοσκελές τρίγωνο αποτελείται από δύο κλαδιά του ίδιου μήκους, ας πούμε ~l~, και ένα τρίτο κλαδί μήκους μεταξύ ~1~ και ~2l - 1~ συμπεριλαμβανομένων. Σημειώστε ότι τα τρίγωνα πρέπει να υπακούουν αυστηρά στην τριγωνική ανισότητα, και τα ισόπλευρα τρίγωνα είναι αποδεκτά. Κάθε κλαδί μπορεί να χρησιμοποιηθεί το πολύ σε ένα τρίγωνο.

Η Αλίκη θα θα ήθελε να μάθει τον μέγιστο αριθμό ισοσκελών τριγώνων που μπορεί να φτιάξει με τα κλαδάκια της.

Υπάρχουν ~Q~ γεγονότα που αλλάζουν τη συλλογή των κλαδιών που έχει η Αλίκη. Το ~i~-οστό γεγονός αποτελείται από δύο ακέραιους αριθμούς ~l_{i}~ και ~d_{i}~, που αντιστοιχούν στο ότι ο αριθμός των κλαδιών μήκους ~l_{i}~ αλλάζει κατά ~d_{i}~. Σημειώστε ότι ο ~d_{i}~ μπορεί να είναι θετικός, αρνητικός ή ακόμη και ~0~, αλλά η Αλίκη δεν θα έχει ποτέ αρνητικό αριθμό κλαδιών ή περισσότερα από ~10^{9}~ κλαδιά από κάθε μήκος.

Ο στόχος σας είναι να προσδιορίσετε τον μέγιστο αριθμό ισοσκελών τριγώνων που μπορεί να φτιάξει η Αλίκη μετά από κάθε συμβάν, αν χρησιμοποιήσει τα κλαδιά της με τον βέλτιστο τρόπο.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει δύο ακέραιους αριθμούς ~N~ και ~Q~ χωρισμένους με κενό διάστημα.

Η δεύτερη γραμμή της εισόδου θα περιέχει Ν ακέραιους αριθμούς ~c_{1}~, ~c_{2}~, ~. . .~ , ~c_{N}\;(0 \le c_{i} \le 10^{9})~ χωρισμένους με κενά διαστήματα, που αντιπροσωπεύουν την αρχική συλλογή της Αλίκης.

Οι επόμενες ~Q~ γραμμές της εισόδου θα περιέχουν η κάθε μία δύο ακέραιους αριθμούς χωρισμένους με κενό διάστημα ~l_{i}~ και ~d_{i}\;(1 \le l_{i} \le N,\; -10^{9} \le d_{i} \le 10^{9})~, που αντιπροσωπεύουν ένα γεγονός.

Αρχικά και μετά από κάθε γεγονός, ο αριθμός των κλαδιών μήκους ~l~ θα είναι μεταξύ ~0~ και ~10^{9}~ για όλα τα ~l = 1, . . . , N~.

Για ~5~ από τους διαθέσιμους βαθμούς, ~2 \le N,Q \le 2000~ και υπάρχουν το πολύ ~2000~ κλαδιά συνολικά αρχικά και μετά από κάθε γεγονός.

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

Για επιπλέον ~5~ από τους διαθέσιμους βαθμούς, ~2 \le N,Q \le 200\;000~ και ο αριθμός των κλαδιών κάθε μήκους είναι είτε ~0~, ~1~ ή ~2~ αρχικά και μετά από κάθε γεγονός.

Για επιπλέον ~5~ από τους διαθέσιμους βαθμούς,~2 \le N.Q \le 200\;000~ και για κάθε γεγονός, ~|d_{i}| = 1~.

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

Έξοδος

Εξάγετε ~Q~ γραμμές που να περιέχουν έναν ακέραιο αριθμό η καθεμία, την απάντηση μετά από κάθε γεγονός.

Παράδειγμα

input

4 3
3 1 4 1
3 -3
1 6
2 1

output

1
3
4

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

Μετά το πρώτο γεγονός, η Αλίκη μπορεί να φτιάξει ένα τρίγωνο με κλαδιά με μήκη (~1~, ~1~, ~1~).

Μετά το δεύτερο γεγονός, η Αλίκη μπορεί να φτιάξει ~3~ τρίγωνα με κλαδιά με μήκη (~1~, ~1~, ~1~).

Μετά το τρίτο γεγονός, η Αλίκη μπορεί να φτιάξει ~3~ τρίγωνα με κλαδιά με μήκη (~1~, ~1~, ~1~) και ένα τρίγωνο με κλαδιά με μήκη (~2~, ~2~, ~3~).