#2509. 送分题

题目描述

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

输入格式

第1行为两个正整数 N ， M 。

接下来 M 行，每行4个非负整数 x 1， y 1， x 2， y 2（0≤ x 1≤ x 2≤ N ，0≤ y 1≤ y 2≤ 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，并保证任意两条线段没有重合部分。