题目描述

给出平面上的 $M$ 条平行于坐标轴的线段，问有多少个正方形。

输入格式

第 $1$ 行为两个正整数 $N，M$ 。 接下来 $M$行，每行 $4$ 个非负整数 $x_{1}，y_{1}，x_{2}，y_{2}(0 \le x_{1} \le x_{2} \le N，0 \le y_{1}\le y_{2} \le N)$ ，描述了线段的两个端点。

输出格式

仅包括一个正整数，为平面上正方形的个数。

3 8
0 0 0 3
1 0 1 3
2 0 2 2
3 0 3 3
0 0 3 0
0 1 3 1
0 2 3 2
0 3 3 3

11

提示

样例对应了如下一张图: 其中边长为 $1$ 的正方形有 $7$ 个，边长为 $2$ 的正方形有 $3$ 个，边长为 $3$ 的正方形有 $1$个。

所以答案为 $7+3+1=11$ 。

数据规模

对于 $20\%$ 的数据，有 $N\le30$ ；

对于 $40\%$ 的数据，有 $N\le100$ ；

对于 $60\%$ 的数据，有 $N\le800$ ；

对于 $100\%$ 的数据，有 $N\le1000，M\le400000$ ，并保证任意两条线段没有重合部分。

题目来源

2011福建集训