Треугольники на удивление величественны. Известно, что круг ребенок может обвести в возрасте 3 лет, квадрат — в 4 года, но чтобы нарисовать треугольник, требуется еще один год (Ан Хё-соп, Син Хи-ён, «Педиатрия Хон Чхан-и», Мирээн (2020), 12-е издание).

Поскольку Иха уже давно перешагнул пятилетний возраст, он без труда нарисовал на бумаге ручкой «большой равносторонний треугольник» с длиной стороны $m$.

Прежде чем удовлетворить любопытство Ихи, необходимо дать определение треугольной сетке. В отличие от прямоугольной системы координат на плоскости, где ось $x$ перпендикулярна оси $y$, в треугольной сетке угол между осью $x$ и осью $y$ составляет 60 градусов. Если провести здесь прямую вида $x+y = m$, то получится равносторонний треугольник с вершинами в точках $(0,0)$, $(m,0)$ и $(0,m)$, как показано на рисунке ниже. Назовем этот равносторонний треугольник «большим равносторонним треугольником».

Рисунок F.1: Оси треугольной сетки и прямая вида $x+y = m$

Иха захотел нарисовать еще больше равносторонних треугольников, поэтому он провел $q$ прямых, каждая из которых параллельна одной из трех сторон и проходит внутри большого равностороннего треугольника, а затем стер части, которые не содержатся внутри большого равностороннего треугольника. В результате равносторонние треугольники расцвели, словно цветы!

Иха был счастлив, глядя на множество равносторонних треугольников, но вскоре ему стало любопытно, сколько всего равносторонних треугольников на рисунке. Поскольку их кажется слишком много, чтобы сосчитать вручную, давайте напишем программу, которая ответит на вопрос Ихи.

Входные данные

В первой строке через пробел задаются целое число $m$, обозначающее длину стороны большого равностороннего треугольника, и количество новых прямых $q$, проведенных Ихой ($1 \le m \le 200\,000$, $0 \le q \le 3m-3$). Вершинами большого равностороннего треугольника в треугольной сетке являются точки $(0,0)$, $(m,0)$ и $(0,m)$.

В следующих $q$ строках через пробел задаются по два целых числа $d$ и $l$ ($0 < l < m$). Здесь $d$ обозначает угол, образуемый прямой с осью $x$, и принимает одно из значений: $0$, $60$ или $120$. Если $d = 0$, добавляется прямая $y = l$; если $d = 60$, добавляется прямая $x = l$; если $d = 120$, добавляется прямая $x+y = l$. Все заданные во входных данных прямые различны.

Выходные данные

Выведите количество равносторонних треугольников, находящихся внутри большого равностороннего треугольника. Треугольники, которые находятся внутри большого треугольника лишь частично, не учитываются. Точка не считается равносторонним треугольником. Сам большой равносторонний треугольник также считается находящимся внутри себя.

Примеры

Входные данные 1

2 3
0 1
60 1
120 1

Выходные данные 1

5

Входные данные 2

10 5
60 1
120 2
0 1
120 5
60 9

Выходные данные 2

12

Примечание

Если нарисовать треугольную сетку и прямые для двух примеров, они будут выглядеть следующим образом.

Рисунок F.2: Рисунок, соответствующий Примеру 1

Рисунок F.3: Рисунок, соответствующий Примеру 2