Xếp hạng

Kỳ thi lập trình có \(N\) đội tham dự được đánh số từ \(1\) đến \(N\). Theo quy định của ban tổ chức, số điểm cuối cùng của một đội nhận được là hai chỉ số \((a, b)\) lần lượt là số bài tập đội đó giải được và tổng số điểm phạt của tất cả các bài đã giải. Điểm phạt cho một bài của mỗi đội được tính qua số lần nộp không thành công bài đó. Khi bắt đầu cuộc thi, tất cả các đội có điểm số là \((0, 0)\).

Xét hai đội \(X_1\) và \(X_2\) lần lượt có điểm số là \((a_1, b_1)\) và \((a_2, b_2)\). Đội \(X_1\) được xem là có điểm số tốt hơn đội \(X_2\) nếu \(a_1 > a_2\) hoặc khi \(a_1 = a_2\) và \(b_1 < b_2\). Một đội được xếp hạng \(H\) nếu có \(H-1\) đội có điểm số tốt hơn đội đó.

Khi có một đội nộp thành công một bài, ban tổ chức sẽ thông báo cho tất cả các đội biết đội nào đã nộp thành công và điểm phạt cho bài nộp thành công của đội đó. Bạn là thành viên của đội số \(1\) và muốn biết thứ hạng của đội mình mỗi khi có đội nộp thành công bài.

Yêu cầu: Hãy viết chương trình cho biết thứ hạng của đội \(1\) mỗi khi có đội nộp bài thành công.

Input

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên \(N\), \(M\) lần lượt cho biết số đội tham dự và số lần một đội nộp bài thành công.

• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(T\), \(P\) (\(1 \le T \le N\) và \(1 \le P \le 1000\)) cho biết đội \(T\) đã nộp một bài thành công và có điểm phạt cho bài nộp này là \(P\). Các lần thông báo được cho theo thứ tự thời gian nộp bài tăng dần.

Ràng buộc:

• \(40\%\) số điểm của bài: \(1 \le N, M \le 100\) và mỗi đội giải thành công tối đa một bài.

• \(80\%\) số điểm của bài: \(1 \le N, M \le 1000\).

• \(100\%\) số điểm của bài: \(1 \le N, M \le 100\,000\).

Output

In ra với mỗi sự kiện nộp bài thành công hãy xuất một số nguyên trên một dòng cho biết thứ hạng của đội \(1\) vào ngay sau thời điểm đó.

Example

Input:

3 5
2 4
3 2
1 3
1 8
2 7

Output:

2
3
2
1
1

Note

Điểm số của các đội \((1, 2, 3)\) sau từng sự kiện:

• Sau \((2, 4)\): \((0,0)\), \((1,4)\), \((0,0)\). Đội \(2\) tốt hơn đội \(1\), thứ hạng của đội \(1\) là \(2\).

• Sau \((3, 2)\): \((0,0)\), \((1,4)\), \((1,2)\). Có hai đội tốt hơn, thứ hạng là \(3\).

• Sau \((1, 3)\): \((1,3)\), \((1,4)\), \((1,2)\). Chỉ đội \(3\) tốt hơn (cùng \(1\) bài nhưng phạt ít hơn), thứ hạng là \(2\).

• Sau \((1, 8)\): \((2,11)\), \((1,4)\), \((1,2)\). Đội \(1\) giải nhiều bài nhất, thứ hạng là \(1\).

• Sau \((2, 7)\): \((2,11)\), \((2,11)\), \((1,2)\). Đội \(2\) có điểm số bằng đội \(1\) nên không tốt hơn, thứ hạng vẫn là \(1\).