小男孩 Alex 非常喜欢折纸。他没日没夜地用纸张折出各种奇奇怪怪的形状。当 Alex 开始折一个新的形状时，他会进行以下操作：

• 他拿一张大小为 $n \times n$ 的正方形纸片，并将其放入笛卡尔平面中，使得正方形的中心位于原点 $(0, 0)$，且纸片的边与坐标轴平行。
• 之后，他进行几次折叠。

在进行折叠时，他选择一条有向直线 $l$，将位于 $l$ 左侧的图形部分翻折到 $l$ 右侧的图形部分之上。更多细节请参考输入格式。

在进行了 $k$ 次折叠后，Alex 想知道最终图形的面积占初始正方形纸片面积的百分之几。请帮助他计算出这个结果。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 100$，$1 \le k \le 5$），分别表示原始正方形纸片的边长和 Alex 进行的折叠次数。

接下来的 $k$ 行描述折叠。每个描述包含四个整数 $x_1, y_1, x_2, y_2$（$-100 \le x_1, x_2, y_1, y_2 \le 100$），定义了一条有向折痕线 $l$。保证点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 是不同的。

图形的左侧部分会被折叠到右侧部分之上。为了确定哪一侧是左侧，哪一侧是右侧，你可以想象自己站在点 $(x_1, y_1)$，面向点 $(x_2, y_2)$ 的方向看去，你的左手边即为左侧，右手边即为右侧。请注意，根据此定义，点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的顺序非常重要。

折痕线 $l$ 有可能完全不与图形相交。这种情况的处理方式很自然：如果图形整个位于 $l$ 的左侧，它将沿折叠线进行镜像对称（翻折）；如果它整个位于 $l$ 的右侧，则什么也不会发生。

输出格式

输出的第一行必须包含一个 $0$ 到 $100$ 之间的整数，表示最终图形面积占初始纸片面积的百分比。

如果你的答案与实际比例（未四舍五入为整数百分比的值）相差不超过 $1\%$，则将被视为正确。

样例

输入样例 1

10 3
0 0 5 5
0 0 0 5
-5 5 -5 -5

输出样例 1

38

输入样例 2

10 1
-5 -5 1 4

输出样例 2

67