题目描述

三角形出人意料地伟大。据说，儿童在 3 岁时便能临摹圆形，4 岁时能画正方形，而画三角形通常还要再晚一年。

Yi-ha 早已年满 5 岁，因此他毫不费力地用笔在纸上画出了一个边长为 $m$ 的“大等边三角形”。

在继续描述之前，先定义三角网格。与直角坐标系中 $x$ 轴和 $y$ 轴互相垂直不同，三角网格中两轴的夹角为 $60^\circ$。再画出直线 $x+y=m$，便得到一个顶点为 $(0,0)$、$(m,0)$、$(0,m)$ 的等边三角形。称其为“大等边三角形”。

图 F.1：三角网格的两条坐标轴与直线 $x+y=m$。

为了画出更多等边三角形，Yi-ha 又画了 $q$ 条直线。每条直线都与大等边三角形的一条边平行，并穿过其内部。随后，他擦除了所有位于大等边三角形外部的线段。

现在图中出现了大量等边三角形。请计算其中完整位于大等边三角形内部的等边三角形总数。

输入格式

第一行包含两个整数 $m,q$，分别表示大等边三角形的边长和新画直线的数量。$(1\le m\le 200000,\ 0\le q\le 3m-3)$

接下来 $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 对应的网格与直线。