Bounding Boxes Positions

A rectangle in a 2D plane with non-zero area is called a non-degenerate rectangle. A degenerate rectangle in a 2D plane is effectively a single segment or a point. In this problem we will consider only non-degenerate rectangles.
Axis aligned rectangle is a rectangle each of which sides is parallel to x or y coordinate axis.

Let A and B be two axis aligned rectangles with non-zero area. Depending on their location in the plane, A and B can be in various relative positions. We will divide all possible relative positions of two axis aligned rectangles into 8 cases listed below.
1. A and B are identical.
2. The boundary of one rectangle lies completely in the interior of the other rectangle.
3. The interior of one rectangle lies completely in the interior of the other rectangle and the borders of the rectangles share at least one point.
4. A lies completely outside of B.
5. The interiors of A and B do not intersect and both rectangles share at least one common point on their borders.
6. Exactly one corner point of one rectangle lies in the interior of the other rectangle and simultaneously exactly one corner point of the other rectangle lies in the interior of the first rectangle.
7. For at least one of the rectangles it holds that exactly two of its corner points lie outside the other rectangle.
8. The borders of the rectangles instersect one another in exactly four distinct points.

Note that cases 1. - 8. list all possibilites, that is, the relative position of any two axis aligned rectangles in a plane always falls into one of the categories 1. - 8. Also note that each pair of cases is mutually exclusive, i.e. mutual position of any two rectangles fall into exactly one case 1. - 8. 1
Image 1 illustrates some possible relative positions in cases 1. - 8.



Image 1. Some examples illustrating possible relative positions of two axis aligned rectangles. Labels 1) - 8) correspond to cases 1. - 8. specified in the text above.

Let E, F, G be three pairwise distinct points in the plane. The bounding box of E, F, G is an axis aligned rectangle R, such that no one of points E, F, G lies outside R and the area of R is minimum possible. Image 2 below illustrates bounding boxes of some triples of points.



Image 2. Some bounding boxes of triples of points of a given set of points. The triple of points and its bounding box is highlighted in blue in all cases a) - f).

The task

A set of pairwise distinct points in the plane is given. Consider each pair of distinct triples of points which bounding boxes are non-degenerate and decide to which case 1. - 8. the relative position of the two bounding boxes belongs. Count how many pairs fall into each of the cases 1. - 8.
Two triples of points are distinct if they differ in at least one point.

Input

The first input line contains one integer N, the number of input points.
Next, there are N lines, each contains one point coordinates. Each line contains x and y coordinate separated by space.
It holds 4 ≤ N ≤ 20. All coordinates are non-negative and less than 15.

Output

The output contains eight lines, each line corresponds to one of the cases 1. - 8. listed above. The cases are listed in ascending order. The lines contains one integer denoting the number of the case and another integer separated by space and denoting the number of pairs of non-degenerate boundig boxes of points triples which mutual position falls into this particular case.

Example 1

Input
6
1 4
2 1
3 4
4 3
6 2
7 5
Output
1 4
2 4
3 70
4 2
5 18
6 14
7 78
8 0

Example 2

Input
4
1 1
3 6
7 2
4 3
Output
1 0
2 0
3 3
4 0
5 0
6 0
7 3
8 0

Example 3

Input
16
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
Output
1 5808
2 208
3 56624
4 4576
5 27984
6 968
7 42704
8 256

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set