Tima 有一个 $N \times N$ 的棋盘，其中有 $K$ 个子矩形被涂成了黑色，其余部分为白色。棋盘的子矩形是指边与棋盘边平行、且顶点坐标为整数的矩形区域。行从上到下编号，列从左到右编号，均从 $1$ 到 $N$。

如果一个棋盘可以被划分为若干个相同的正方形（边长大于或等于 $1$ 且严格小于 $N$），且每个正方形内部的所有格子颜色相同，相邻的正方形颜色不同，我们就称该棋盘为“棋盘格”。两个正方形如果有一条公共边，则称它们是相邻的。下图展示了 $N = 6$ 时所有可能的棋盘格：

每次重涂，Tima 可以改变一个格子的颜色。如果该格子原来是白色，重涂后将变为黑色，反之亦然。Tima 要得到一个棋盘格，最少需要重涂多少次？

输入格式

第一行包含两个整数 $N, K$ ($2 \le N \le 10^5, 0 \le K \le \min(N^2, 10^5)$)，分别表示棋盘的边长和黑色子矩形的数量。接下来的 $K$ 行，每行包含四个整数 $x_{1i}, y_{1i}, x_{2i}, y_{2i}$ ($1 \le x_{1i}, y_{1i}, x_{2i}, y_{2i} \le N, x_{1i} \le x_{2i}, y_{1i} \le y_{2i}$)，表示第 $i$ 个黑色子矩形的左上角和右下角坐标。保证任意两个子矩形不相交。

输出格式

输出一个整数，表示得到棋盘格所需的最少重涂次数。

子任务

本题包含六个子任务：

1. $2 \le N \le 100, K = 0$。分值为 8 分。
2. $N$ 为质数，且每个子矩形的面积等于 $1$。分值为 8 分。
3. $2 \le N \le 100, 0 \le K \le \min(N^2, 1000)$。每个子矩形的面积等于 $1$。分值为 15 分。
4. $2 \le N \le 1000, 0 \le K \le \min(N^2, 10^5)$。每个子矩形的面积等于 $1$。分值为 16 分。
5. $2 \le N \le 10^5, 0 \le K \le \min(N^2, 10^5)$。每个子矩形的面积等于 $1$。分值为 23 分。
6. $2 \le N \le 10^5, 0 \le K \le \min(N^2, 10^5)$。分值为 30 分。

样例

输入 1

2 0

输出 1

2

输入 2

6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6

输出 2

14

输入 3

4 1
4 1 4 4

输出 3

8

说明