2509 - 送分题

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

输入

第1行为两个正整数N,M。 接下来M行,每行4个非负整数x1,y1,x2,y2(0≤x1≤x2≤N,0≤y1≤y2≤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≤30;

对于40%的数据,有N≤100;

对于60%的数据,有N≤800;

对于100%的数据,有N≤1000,M≤400000,并保证任意两条线段没有重合部分。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题