Jagoda

Ο Slavko έχει ~N~ κουνέλια που τα ταΐζει καθημερινά με διάφορα φρούτα και λαχανικά. Τα κουνέλια, ωστόσο, προτιμoύν τις φράουλες πάνω από όλα. Οι φράουλες είναι δυσεύρετες και ακριβές στη μέση του χειμώνα, οπότε ο Slavko δίνει φράουλες μόνο σε μερικά από τα κουνέλια του.
Ο Slavko αρίθμησε τα κουνέλια από το ~1~ έως το ~N~. Για να παρακολουθείτε πόσες φράουλες κάθε ένα από τα κουνέλια πήραν, ο Slavko αποφάσισε την ακόλουθη διαδικασία κατανομής φράουλας.
Κάθε μέρα ο Slavko αγοράζει έναν αριθμό ~S~ φράουλες και επιλέγει ένα κουνέλι ~A~ για να πάρει την πρώτη φράουλα. Το κουνέλι ~A+1~ θα πάρει τη δεύτερη φράουλα, το κουνέλι ~A+2~ την τρίτη κ.λπ.
Σε κάθε κουνέλι εκχωρείται ένα αρχικά άδειο σπιρτόκουτο, με τα ~N~ σπιρτόκουτα να σχηματίζουν μια ενιαία σειρά.
Έστω ~K~ ο μεγαλύτερος ακέραιος έτσι ώστε ~K \cdot K \le N~. Κάθε ομάδα ~K~ σπιρτόκουτων (ξεκινώντας από το πρώτο) θα έχει και ένα φλιτζάνι δίπλα της. Λέμε ότι ~K~ διαδοχικά σπιρτόκουτα με την κούπα τους σχηματίζουν ένα μπλοκ.
Αφού δώσει στα κουνέλια τις φράουλες τους, ο Slavko θα βάλει ένα σπίρτο στο σπιρτόκουτο του κάθε κουνελιού που πήρε μια φράουλα, εκτός κι αν έβαζε ένα σπίρτο σε όλα τα σπιρτόκουτα σε ένα μπλοκ. Αντί να βάλει σπίρτα σε όλα τα σπιρτόκουτα σε ένα μπλοκ, θα βάλει ένα σπίρτο στο κατάλληλο φλιτζάνι.
Ο συνολικός αριθμός των φραουλών που έλαβε ένα κουνέλι μπορεί να υπολογιστεί ως ο αριθμός των σπίρτων στο σπιρτόκουτό του συν τον αριθμό των σπίρτων στο φλιτζάνι του.

Για παράδειγμα, υποθέστε ότι υπάρχουν 11 κουνέλια, δηλαδή ~N=11~. Ο αριθμός τρία είναι ο μεγαλύτερος ακέραιος αριθμός που όταν τετραγωνιστεί δίνει αποτέλεσμα ~\le 11~, άρα ~K=3~. Θα υπάρχουν τέσσερα μπλοκ, το τελευταίο από αυτά ελλιπές με μόνο δύο σπιρτόκουτα. Αν ο Slavko αγοράσει 6 φράουλες και δώσει την πρώτη από αυτές στο κουνέλι 5, η κατάσταση στα κύπελλα και τα σπιρτόκουτα θα είναι:

Γράψτε ένα πρόγραμμα που προσομοιώνει την παραπάνω διαδικασία, γνωρίζοντας τον αριθμό των κουνελιών ~N~, τον αριθμό των ημερών ~M~ και τους αριθμούς ~S~ και ~A~ για καθεμία από τις ~M~ ημέρες.
Για κάθε μέρα, τυπώστε τον συνολικό αριθμό σπίρτων σε όλα τα σπιρτόκουτα και τα φλιτζάνια στα οποία πρόσθεσε ο Slavko σπίρτα εκείνη την ημέρα.

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους ~N~ και ~M~ που χωρίζονται από ένα κενό ~(1 \le N,\; M \le 100\,000)~, τον αριθμό των κουνελιών και μερών.
Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει δύο ακέραιους αριθμούς ~S~ και ~A~ που χωρίζονται από ένα κενό. Αυτοί οι αριθμοί σημαίνουν ότι ο Slavko αγόρασε ~S~ φράουλες εκείνη την ημέρα και ότι το κουνέλι ~A~ θα λάβει την πρώτη ~(1 \le A \le N, \; 1 \le A+S-1 \le N)~.

Έξοδος

Τυπώστε ~M~ αριθμούς, τον καθένα σε ξεχωριστή γραμμή. Η ~k~-η γραμμή θα πρέπει να περιέχει τον συνολικό αριθμό σπίρτων σε όλα τα σπιρτόκουτα και τα φλιτζάνια που χρησιμοποίησε ο Slavko την ημέρα ~k~.

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

input

11 3
6 5
3 1
11 1

output

4
1
6

input

16 3
2 2
12 3
6 11

output

2
7
3

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

1. Την πρώτη μέρα, ο Slavko δίνει φράουλες στα κουνέλια 5 έως 10, βάζοντας σπίρτα στα σπιρτόκουτα 5, 6 και 10 και ένα στο τρίτο φλιτζάνι. Πριν από αυτό δεν υπήρχαν άλλα σπίρτα στα σπιρτόκουτα και τα φλιτζάνια που χρησιμοποίησε, οπότε η έξοδος είναι τέσσερα.
2. Τη δεύτερη μέρα, ο Slavko δίνει φράουλες στα κουνέλια 1 έως 3, βάζοντας μόνο ένα σπίρτο στο πρώτο φλιτζάνι.
3. Την τρίτη μέρα, ο Slavko δίνει φράουλες σε όλα τα κουνέλια του, βάζοντας ένα σπίρτο σε κάθε φλιτζάνι. Αφού έβαλε τα τέσσερα σπίρτα σε φλιτζάνια, υπάρχουν συνολικά έξι σπίρτα στα φλιτζάνια που χρησιμοποίησε, έτσι η έξοδος είναι έξι.