두 개의 지도

닥터 스트레인지는 티베트에 있는 에인션트 원의 성을 찾으러 간다. 지도가 없으면 한 걸음도 나아갈 수 없다.

티베트는 직선 위에 놓여 있다. 닥터는 지도를 여러 장 가지고 있고, 각 지도는 이 직선의 한 구간을 보여 준다. 닥터 스트레인지는 지도를 정확히 두 장 가져간다. 이 두 지도가 보여 주는 티베트 영역의 길이는 $s$와 같아야 한다. 이 영역은 연속일 필요가 없다. 어떤 부분이 두 지도에 모두 나타나 있다면, 그 부분은 한 번만 센다.

여행을 떠나기 전에 닥터는 새 지도를 사고 낡은 지도를 판다. 컬렉션이 바뀔 때마다 위 조건을 만족하는 지도 두 장을 고르는 방법이 몇 가지인지 알고 싶다.

첫 줄에 정수 $s$와 $n$이 주어진다. $s$는 관심 있는 길이이고, $n$은 컬렉션을 바꾸는 횟수이다 ($1 \le s \le 10^9$, $1 \le n \le 10^5$).

이어지는 $n$개의 줄마다 사건이 하나씩 주어진다.

• 1 l_i r_i 형태의 줄은 닥터가 티베트의 $l_i$부터 $r_i$까지를 보여 주는 새 지도를 샀다는 뜻이다 ($l_i < r_i$).
• 2 k 형태의 줄은 닥터가 사건 번호 $k$에서 얻은 지도를 팔았다는 뜻이다. 사건은 1부터 번호가 매겨진다. 사건 $k$는 항상 타입 1이며, 같은 지도를 두 번 팔 수는 없다.

모든 좌표는 절댓값이 $5\cdot10^8$ 이하인 정수이다. 같은 지도가 여러 장 있을 수 있다. 처음에 닥터는 지도를 가지고 있지 않다.

각 사건이 끝난 뒤, 두 지도가 보여 주는 티베트 영역의 길이가 $s$와 같아지도록 지도 두 장을 고르는 방법의 수를 출력한다.