Thư viện của Viện bảo tàng Thời trang có tổng cộng ~2n~ cuốn sách, được đánh số từ ~1~ đến ~2n~ và xếp trên giá theo thứ tự tăng dần mã số từ trái sang phải (vị trí ~1~ đến ~2n~).

Ban đầu:

• ~n~ cuốn đầu tiên (mã ~1..n~) là sách lịch sử thời trang.
• ~n~ cuốn còn lại (mã ~n+1..2n~) là sách thời trang đương đại.

Do hệ thống cảnh báo đang sửa chữa, mỗi lần độc giả lấy 2 cuốn ở hai vị trí ~i~ và ~j~, sau khi đọc xong họ trả ngược vị trí: cuốn lấy từ vị trí ~i~ được đặt vào vị trí ~j~, và cuốn lấy từ vị trí ~j~ được đặt vào vị trí ~i~ (tức là hoán đổi hai cuốn sách ở hai vị trí đó).

Có ~m~ lần như vậy.

Yêu cầu

Sau mỗi lần hoán đổi, hãy xác định có bao nhiêu cuốn sách lịch sử thời trang (tức các cuốn có mã trong đoạn ~[1..n]~) đang nằm trong các vị trí từ ~1~ đến ~n~ trên giá.

Dữ liệu

• Dòng 1: số nguyên ~n~ (~1 \le n \le 10^5~).
• Dòng 2: số nguyên ~m~ (~1 \le m \le 10^5~).
• Trong ~m~ dòng tiếp theo, dòng thứ ~k~ chứa hai số nguyên ~i_k, j_k~ (~1 \le i_k, j_k \le 2n~): hai vị trí bị hoán đổi ở lần thứ ~k~.

Kết quả

In ra ~m~ dòng, dòng thứ ~k~ là số lượng sách lịch sử thời trang vẫn nằm trong các vị trí ~1..n~ sau khi thực hiện hoán đổi ở lần thứ ~k~.

Ví dụ

Ví dụ 1

Input

3
3
1 4
2 5
3 6

Output

2
1
0

Giải thích

Ví dụ 1

Ban đầu, các vị trí ~1..6~ chứa các sách: [1, 2, 3, 4, 5, 6] (trong đó sách lịch sử là ~1,2,3~), nên trong ~1..3~ có ~3~ cuốn lịch sử.

• Lần 1 hoán đổi vị trí ~1~ và ~4~: [4, 2, 3, 1, 5, 6] ⇒ trong ~1..3~ còn ~{2,3}~ ⇒ ~2~.
• Lần 2 hoán đổi vị trí ~2~ và ~5~: [4, 5, 3, 1, 2, 6] ⇒ trong ~1..3~ còn ~{3}~ ⇒ ~1~.
• Lần 3 hoán đổi vị trí ~3~ và ~6~: [4, 5, 6, 1, 2, 3] ⇒ trong ~1..3~ không còn sách lịch sử ⇒ ~0~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10^5~
• ~1 \le m \le 10^5~
• ~1 \le i_k, j_k \le 2n~