종이, 펜, 삼각형

삼각형은 의외로 위대하다. 원은 만 3세면 따라 그릴 수 있고, 사각형은 만 4세면 그릴 수 있다. 그러나 삼각형은 그보다 1년은 더 지나야 그릴 수 있다고 알려져 있다 (안효섭, 신희영, 『홍창의 소아과학』, 미래앤(2020), 12판). 이하는 만 5살이 된지 한참 되었기 때문에 무리 없이 종이에 펜으로 변의 길이가 $m$인 '큰 정삼각형'을 하나 그렸다.

이하의 호기심을 조금 더 알아보기 전에 삼각격자에 대한 정의가 필요하다. 좌표평면에서 $x$축이 $y$축과 직각을 이루는 직각좌표계와는 달리, 삼각격자는 다음 그림과 같이 $x$축과 $y$축이 이루는 각도가 60도이다. 여기에 $x + y = m$ 꼴의 직선을 그으면 다음 그림과 같이 $(0,0)$, $(m,0)$, $(0,m)$을 꼭짓점으로 갖는 정삼각형이 하나 만들어진다. 이 정삼각형을 '큰 정삼각형'이라고 하자.

그림 F.1: 삼각격자의 양 축과 $x+y=m$ 꼴 직선

이하는 더더욱 많은 정삼각형을 그리고 싶어서, 세 변 중 하나에 평행하면서 큰 정삼각형의 내부를 지나가는 직선을 $q$개 그은 다음 큰 정삼각형에 포함되지 않는 부분은 지워 버렸다. 그러자 정삼각형이 꽃처럼 피어났다!

이하는 수많은 정삼각형을 보며 행복해졌으나, 이내 그림에 정삼각형이 총 몇 개나 있는지 궁금해졌다. 손으로 세기에는 너무 많아 보이니, 이하의 질문에 답할 수 있는 프로그램을 작성해 보자.

첫째 줄에는 큰 정삼각형의 한 변의 길이를 나타내는 정수 $m$과 이하가 새로 그은 직선의 개수 $q$가 공백으로 구분되어 주어진다. ($1 \leq m \leq 200\ 000$, $0 \leq q \leq 3m-3$) 큰 정삼각형의 꼭짓점은 삼각격자에서 $(0,0)$, $(m,0)$, $(0,m)$이다.

그 다음 $q$개의 줄에는 각각 두 개의 정수 $d$와 $l$이 공백으로 구분되어 주어진다. ($0 < l < m$) $d$는 $x$축과 이루는 각도를 의미하며 $0$, $60$, $120$ 중 하나이다. $d$가 $0$이면 직선 $y=l$이, $60$이면 직선 $x=l$이, $120$이면 직선 $x+y=l$이 추가된다.

입력으로 들어오는 직선은 모두 다르다.

큰 정삼각형 안에 있는 정삼각형의 개수를 출력한다. 일부만 큰 정삼각형 안에 있는 정삼각형은 포함하지 않으며, 점은 정삼각형이 아니다. 큰 정삼각형도 자기 자신 안에 있다.

두 예제의 삼각격자와 직선을 그려보면 다음과 같다.

그림 F.2: 예제 1에 해당하는 그림	그림 F.3: 예제 2에 해당하는 그림