Trong giờ thực hành môn Tin học thầy Hiếu tổ chức một trò chơi, thầy quyết định chọn ra ~n~ em học sinh nam và ~n~ em học sinh nữ để tham gia trò chơi. Thầy Hiếu yêu cầu các em học sinh xếp thành một hàng dọc, tuy nhiên ~n~ em học sinh nam đã nhanh chân đứng xếp hàng trước ~n~ em học sinh nữ.

Thầy Hiếu quan sát hàng sau khi xếp thấy ~n~ em học sinh nam đã đứng trước ~n~ em học sinh nữ, thầy không hài lòng nên yêu cầu đổi chỗ ~k~ lần. Lần thứ ~i~, thầy đổi chỗ hai em trong hàng ở vị trí ~x~ và ~y~ ~(1 \le i \le k)~. Sau mỗi lần đổi chỗ, thầy rất muốn biết còn bao nhiêu em học sinh nam vẫn đứng ở nửa đầu của hàng.

Yêu cầu: Viết chương trình giúp thầy Hiếu trả lời được câu hỏi trên.

Input

• Dòng 1: Là số nguyên dương ~n~.

• Dòng 2: Là số ~k~ (số lần đổi chỗ).

• Dòng thứ ~i~ trong ~k~ dòng tiếp theo, mỗi dòng ghi ~2~ số ~x, y~ ~(1 \le x, y \le 2n)~.

Output

Ghi ra ~k~ dòng, mỗi dòng một số nguyên là số lượng học sinh nam đứng ở nửa đầu của hàng.

Scoring

Sample Input 1

3
3
1 4
4 6
6 1

Sample Output 1

2
2
3

Notes

• Lần 1: Đổi chỗ ~2~ em ở vị trí ~1~ và ~4~ thì số học sinh nam ở nửa đầu của hàng còn lại là ~2~.

• Lần 2: Đổi chỗ ~2~ em ở vị trí ~4~ và ~6~ thì số học sinh nam ở nửa đầu của hàng còn lại là ~2~.

• Lần 3: Đổi chỗ ~2~ em ở vị trí ~6~ và ~1~ thì số học sinh nam ở nửa đầu của hàng còn lại là ~3~.