초코칩 케이크

2021년도 이제 얼마 남지 않았다. 희노애락의 연속이었던 2021년의 이른 회고를 위해 이하는 직사각형 모양의 케이크를 구매했고 이제 언박싱만을 기다리고 있다. 대칭과 일관성을 중시하는 이하는 케이크를 위에서 볼 때 가로 $n$줄, 세로 $n$줄로 총 $n^2$개의 정사각형 조각이 되도록 제작주문했다. 케이크 상자를 열어보니 이하가 원한 대로 똑같은 크기의 정사각형 조각이 많이 있다. 그러나 이하는 주문할 때 토핑까지는 신경쓰지 못해서, 모든 조각 위에는 아무런 장식이 없어 밋밋해보이기까지 한다. 이하는 맛과 비주얼을 위해 케이크에 초코칩을 다음과 같이 $q$번 올려 장식을 하려 한다.

• 한 가로줄에 있는 모든 조각에 초코칩을 $1$개 올린다.
• 한 세로줄에 있는 모든 조각에 초코칩을 $1$개 올린다.

이하는 초코칩이 아주 많기 때문에, 중간에 초코칩을 올리다 모자라는 일은 없다. 이 수많은 초코칩을 한땀한땀 올리는 이하는 원초적이며 본질적인 의문에 빠지지 않을 수 없었다. 매번 초코칩을 줄에 올릴 때마다 초코칩이 가장 많이 있는 조각의 개수는 어떻게 변할까? 이하가 초코칩을 장인정신으로 올리고 있는 동안 이하의 궁금증을 대신 해결해보자.

첫 번째 줄에 두 정수 $n$, $q$가 공백으로 구분되어 주어진다. $(1 \leq n \leq 30,000, 1 \leq q \leq 100,000)$

$n$은 가로줄과 세로줄의 개수이며, $q$는 장식 횟수이다.

이후로 $q$개의 줄에 두 정수 $t$, $a$가 공백으로 구분되어 주어진다. ($1 \leq t \leq 2,\ 1 \leq a \leq n$)

$t$ 가 $1$이면 $a$번째 가로줄에, $2$이면 $a$번째 세로줄에 있는 모든 조각에 초코칩을 $1$개씩 올린다. 한 번 올린 초코칩은 계속 유지된다.

각 줄마다 매 번 장식을 한 이후 케이크에 초코칩이 가장 많이 있는 조각의 개수를 출력한다.