Thế là chủ một trang trại bò. Do ảnh hưởng của dịch covid, những con bò của Thế ngày càng trở nên buồn bã. Lo lắng cho những chú bò, Thế quyết định sẽ lắp internet cho hệ thống trang trại của mình để chúng có thể lướt web xem phim và chatchit.

Thế quyết định xây dựng một hệ thống mạng LAN cho những chiếc chuồng bò. Ban đầu, không có cặp chuồng bò nào được kết nối với nhau. Trong ~Q~ ngày tiếp theo, ngày thứ ~i~, Thế dự định sẽ thiết lập một số kết nối giữa các chuồng bò trong đoạn ~[L_i, R_i]~. Cụ thể các cặp chuồng bò sau sẽ được kết nối với nhau:

~(L_i, R_i)~, ~(L_i + 1, R_i - 1)~, ~(L_i + 2, R_i - 2)~, ..., ~(R_i, L_i).~

Nói cách khác, trong ngày thứ ~i~, một kết nối trực tiếp sẽ được thiết lập giữa hai chuồng bò ~(L_i + k, R_i - k)~ với mọi ~k~ thỏa mãn ~0 \le k \le R_i - L_i~.

Hai chuồng bò được gọi là chung nhóm với nhau nếu chúng có kết nối trực tiếp với nhau, hoặc gián tiếp qua một số chuồng bò khác. Nhiệm vụ của bạn là tìm ra số lượng nhóm các chuồng bò sau mỗi ngày thứ ~i (1 \leq i \leq Q)~.

Input

Dòng đầu tiên gồm hai số nguyên dương ~N (2 \le N \le 2 \cdot 10^{5})~ và ~Q~ ~(1 \le Q \le 5 \cdot 10^{5})~ - số lượng chuồng bò và số ngày Thế dự định xây dựng mạng LAN.

Mỗi dòng trong ~Q~ dòng tiếp theo chứa hai số nguyên dương ~L_i~ và ~R_i~ ~(1 \le L_i \le R_i \le N)~ mô tả kế hoạch dựng mạng của Thế trong ngày thứ ~i~.

Output

In ra ~Q~ dòng, dòng thứ ~i~ là số nhóm chuồng bò sau khi Thế thực hiện xong kế hoạch của ngày thứ ~i~.

Example

5 3
1 4
3 5
1 5

3
2
1