Степан проводить змагання з ~N~ гравцями, пронумерованими від 1 до ~N~. Гравці змагатимуться за очки. Наразі всі гравці мають нуль очок.

Здатність Степана передбачати дозволяє йому знати, як зміняться результати гравців. Зокрема, для ~i=1,2,…,T~ рахунок гравця ~A_i~ ​ збільшиться на ~B_i~ ​ очок через ~i~ секунд. Інших змін у балах не буде.

Степан, який віддає перевагу різноманітності в балах, хоче знати, скільки різних значень балів зʼявлятиметься серед результатів гравців у кожен момент. Для кожного ~i=1,2,…,T~ знайдіть кількість різних значень очок серед очок гравців на ~i + 0,5~ секунді.

Наприклад, якщо в певний момент гравці мають 10, 20, 30 і 20 очок, серед результатів гравців на цей момент є три різні значення.

Обмеження

• ~1≤N,T≤2×10^5~
• ~1≤A_i ≤N~
• ~1≤B_i ≤10^9~
• Усі вхідні значення є цілими числами

Формат вхідних даних

Перший рядок містить цілі числа ~N,T~.

Наступні  ~T~ рядків містять цілі числа ~A_i, B_i~.

Формат вихідних даних

У вихідний потік виведіть ~Т~ рядків.

~i~-й рядок (~1≤i≤T~) має містити ціле число - кількість різних значень очок серед очок гравців на ~i + 0,5~ секунді.

Приклад вхідних даних

3 4
1 10
3 20
2 10
2 10

Приклад вихідних даних

2
3
2
2

Нехай ~S~ буде послідовністю очок гравців 1, 2, 3 у такому порядку. Наразі ~S=\{0,0,0\}~.

• Через одну секунду рахунок гравця 1 збільшується на 10 очок і ~S=\{10,0,0\}~. Таким чином, через 1,5 секунди серед результатів гравців є два різні значення.
• Через дві секунди рахунок гравця 3 збільшується на 20 очок і ~S=\{10,0,20\}~. Таким чином, через 2,5 секунди серед результатів гравців є три різні значення.
• Через три секунди рахунок гравця 2 збільшується на 10 очок і ~S=\{10,10,20\}~. Таким чином, через 3,5 секунди серед результатів гравців є два різні значення.
• Через чотири секунди рахунок гравця 2 збільшується на 10 очок і ~S=\{10,20,20\}~. Таким чином, через 4,5 секунди серед результатів гравців є два різні значення.

Приклад вхідних даних

1 3
1 3
1 4
1 3

Приклад вихідних даних

1
1
1

Приклад вхідних даних

10 10
7 2620
9 2620
8 3375
1 3375
6 1395
5 1395
6 2923
10 3375
9 5929
5 1225

Приклад вихідних даних

2
2
3
3
4
4
5
5
6
5