Squarefinder – Locating regular tetragons Imagine a bunch of rectangles drawn in the plane, each rectangle with its vertices at integer coordinates and its sides parallel to the axes:



The rectangles partition the plane into a number of disjoint regions, coloured red and blue below:



Your goal is to find the number of such regions which are perfect squares. In the example above, there are three:



Note that the big square in the middle is not counted as it is not a single region, but is instead made up of several smaller disjoint regions.

Input

You may write a function or a full program for this challenge.

Input will be 4n nonnegative integers defining n rectangles in the plane. Each rectangle is represented by two opposing vertices, e.g. 4 9 7 8 represents the rectangle with opposing vertices (4, 9) and (7, 8). Note that this rectangle could also be represented as 7 8 4 9 or 4 8 7 9.

The exact input format is flexible (e.g. space-separated string, comma-separated string, single array of integers, list of coordinate tuples, and so on) but please be reasonable and give an example of how to run your code in your post. You may not reorder the input.

For simplicity, you can assume that no two edges will be overlapping — this includes overlapping at a vertex. In particular, this implies that no two rectangles will be touching edge-to-edge or corner-to-corner, and the rectangles will have nonzero area.

Output

Your program should print or return a single integer, which is the number of square regions.

Scoring

This is code golf, so the code in the fewest bytes wins.



Test cases

Input:

0 0 5 5
6 8 10 4
14 16 11 13
19 1 18 2


Output:

4


This is simply four disjoint squares:





Input:

2 1 3 11
1 10 5 19
6 10 11 3
8 8 15 15
13 13 9 5
15 1 19 7
17 19 19 17


Output:

3


This is the example test case at the start of the post.



Input:

0 9 15 12
6 3 18 15
9 6 12 20
13 4 17 8


Output:

7






Input:

5 9 11 10
5 12 11 13
6 8 7 14
9 8 10 14
13 8 14 9
13 10 14 14


Output:

14






Input:

0 99999 100000 0


Output:

0


This is just one big rectangle.



Input:

0 99999 100000 0
2 1 142857 285714


Output:

1


Two big rectangles which overlap.
Python 2, 480 436 386 352 bytes

exec u"""s=sorted;H=[];V=[]
FRIinput():
 S=2*map(s,zip(*R))
 FiI0,1,2,3:
    c=S[i][i/2];a,b=S[~i]
    FeIs(H):
     C,(A,B)=e
     if a&lt;C&lt;b&amp;A&lt;c&lt;B:e[:]=C,(A,c);H+=[C,(c,B)],;V+=[c,(a,C)],;a=C
    V+=[c,(a,b)],;H,V=V,H
print sum(a==A==(d,D)&amp;c==C==(b,B)&amp;B-b==D-d&amp;1-any(d&lt;X[0]&lt;D&amp;b&lt;y&lt;B Fy,XIH)Fb,aIH FB,AIH Fd,cIV FD,CIV)""".translate({70:u"for ",73:u" in ",38:u" and "})


Takes a list of coordinate pairs through STDIN in the format:

[  [(x, y), (x, y)],  [(x, y), (x, y)],  ...  ]


and prints the result to STDOUT.


The actual program, after string replacement, is:

s=sorted;H=[];V=[]
for R in input():
 S=2*map(s,zip(*R))
 for i in 0,1,2,3:
    c=S[i][i/2];a,b=S[~i]
    for e in s(H):
     C,(A,B)=e
     if a&lt;C&lt;b and A&lt;c&lt;B:e[:]=C,(A,c);H+=[C,(c,B)],;V+=[c,(a,C)],;a=C
    V+=[c,(a,b)],;H,V=V,H
print sum(a==A==(d,D) and c==C==(b,B) and B-b==D-d and 1-any(d&lt;X[0]&lt;D and b&lt;y&lt;B for y,X in H)for b,a in H for B,A in H for d,c in V for D,C in V)


Explanation

Instead of fiddling with complex polygons, this program deals with simple line segments.
For each input rectangle, we add each of its four edges to a collective segment list, individually.
Adding a segment to the list goes as follows:
we test each of the existing segments for intersection with the new segment;
if we find an intersection, we divide both segments at the point of intersection and continue.
To make things easier, we actually keep two separate segment lists: a horizonal one and a vertical one.
Since segments don't overlap, horizontal segments can only intersect vertical segments and vice versa.
Better yet, it means that all intersections (not considering the edges of the same rectangle) are "proper," i.e., we don't have T-shaped intersections, so "both sides" of each segment are truly divided.

Once we've constructed the segment list(s), we start counting squares.
For each combination of four segments (particularly, two horizontal segments and two vertical ones,) we test if they form a square.
Furthermore, we verify that no vertex lies within this square (which can happen if, for example, we have a small square inside a bigger one.)
This gives us the desired quantity. Note that even though the program tests each combination four times in different orders, the particular ordering of the segment coordinates guarantees that we count each square only once.