Experimente

Dexter și-a deschis un laborator nou în care vrea să efectueze o serie de experimente pe șoareci pentru a descoperi leacul pentru cancer. În laborator există $N$ șoareci, care se află așezați într-un cerc și sunt numerotați în ordine de la $0$ la $N-1$.

Dexter efectuează, pe rând, $M$ experimente. Pentru fiecare experiment șoarecii care participă la al $i$-lea experiment formează întotdeauna un interval continuu, exprimat sub forma unei perechi de numere $(S_i, F_i)$, având semnificația:

• dacă $S_i \leq F_i$, atunci șoarecii $S_i, S_{i}+1, \ldots, F_i$ participă la experimentul $i$;
• dacă $S_i > F_i$, atunci șoarecii $S_i, S_{i}+1, \ldots, N-2, N-1, 0, \ldots, F_i$ participă la experimentul $i$.

Cerință

La fiecare pas, Dexter vrea să știe câți din cei $N$ șoareci au participat la toate experimentele efectuate până atunci. Altfel spus, după fiecare al $i$-lea experiment efectuat, să se determine numărul de șoareci care au participat la toate experimentele $1, 2, \ldots, i$.

Date de intrare

Fișierul de intrare experimente.in conține pe prima linie două numere $N$ și $M$. Fiecare din următoarele $M$ linii conține două numere $A_i$ și $B_i$, având următoarea semnificație:

• dacă $i = 1$, atunci $S_i = A_i$ și $F_i = B_i$;
• dacă $i > 1$ și notând cu $R_{i-1}$ răspunsul pentru cel de al $(i-1)$-lea experiment, atunci $S_i = (R_{i-1} + A_i) \bmod N$ și $F_i = (R_{i-1} + B_i) \bmod N$.

Date de ieșire

Fișierul de ieșire experimente.out trebuie să conțină $M$ linii. Pe cea de a $i$-a linie se va afișa un singur număr reprezentând numărul de șoareci care au participat la toate experimentele $1, 2, \ldots, i$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000 \ 000$
• $1 \leq M \leq 100 \ 000$
• $0 \leq A_i, B_i < N$

Exemplul 1

experimente.in

5 3
1 4
3 0
2 0

experimente.out

4
3
2

Explicație

Pentru primul experiment $S_1 = 1$ și $F_1 = 4$; participă șoarecii $1$, $2$, $3$ și $4$, deci $R_1 = 4$.

Pentru al doilea experiment, $S_2 = (3 + 4) \bmod 5 = 2$, iar $F_2 = (0 + 4) \bmod 5 = 4$. La primele două experimente participă șoarecii $2$, $3$ și $4$, deci $R_2 = 3$

Pentru al treilea experiment, $S_3 = (2 + 3) \bmod 5 = 0$, iar $F_3 = (0 + 3) \bmod 5 = 3$. La primele trei experimente participă șoarecii $2$ și $3$, deci $R_3 = 2$.

Exemplul 2

experimente.in

6 2
4 1
2 5

experimente.out

4
2

Explicație

Pentru primul experiment $S_1 = 4$ și $F_1 = 1$; participă șoarecii $0$, $1$, $4$ și $5$, deci $R_1 = 4$.

Pentru al doilea experiment, $S_2 = (2 + 4) \bmod 6 = 0$, iar $F_2 = (5 + 4) \bmod 6 = 3$. La primele două experimente participă șoarecii $0$ și $1$, deci $R_2 = 2$.