은하 대학생 프로그래밍 대회

2117년, 국제 대학생 프로그래밍 대회는 규모가 크게 늘어 은하 대학생 프로그래밍 대회(GCPC)가 되었다.

올해 대회에는 팀 $n$개가 참가한다. 팀에는 $1, 2, \ldots, n$번이 붙어 있고, 내가 응원하는 팀은 $1$번 팀이다.

팀의 점수는 정수 쌍 $(a, b)$이다. $a$는 그 팀이 푼 문제 수이고, $b$는 그 팀의 총 페널티다. 문제를 풀면 그 문제에 해당하는 페널티가 붙고, 팀의 총 페널티는 그 팀이 푼 문제의 페널티를 모두 더한 값이다. 페널티 하나를 어떻게 계산하는지는 이 문제에서 중요하지 않다.

두 팀 $t_1$과 $t_2$의 점수가 각각 $(a_1, b_1)$, $(a_2, b_2)$라고 하자. $a_1 > a_2$이거나, $a_1 = a_2$이면서 $b_1 < b_2$이면 $t_1$의 점수가 $t_2$의 점수보다 좋다. 한 팀의 순위는 $k + 1$이고, $k$는 그 팀보다 점수가 좋은 팀의 수다.

주최 측은 순위표를 공개하지 않는다. 대신 어떤 팀이 문제를 풀 때마다 그 사실을 알리는 메시지를 바로 보낸다. 메시지가 올 때마다 $1$번 팀의 순위를 구하라.

첫째 줄에 팀 수 $n$과 이벤트 수 $m$이 주어진다. ($1 \le n \le 10^5$, $1 \le m \le 10^5$)

다음 $m$개 줄에 이벤트가 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $t$와 $p$가 주어지고, $t$번 팀이 페널티가 $p$인 문제를 풀었다는 뜻이다. ($1 \le t \le n$, $1 \le p \le 1000$) 이벤트는 일어난 순서대로 주어진다.

$m$개 줄을 출력한다. $i$번째 줄에는 처음 $i$개의 이벤트가 일어난 뒤 $1$번 팀의 순위를 출력한다.