Several points are given in the plane. The points are numbered consecutively starting from $1$, and each number is assigned to exactly $2$ points, forming a pair. Thus the total number of points is necessarily even. We want to connect two points with the same number by a rectangle for which they are opposite vertices. We call such a rectangle a connecting rectangle. The task is to find several non-overlapping connecting rectangles satisfying the following three conditions.

(Condition 1) The opposite vertices of a connecting rectangle must be points with the same number. Points with different numbers must not be connected by a rectangle.

(Condition 2) All connecting rectangles must be separated from one another. The situation in Figure 1 is not allowed. Neither are situations where the sides or vertices of two connecting rectangles touch, as in Figure 2, or where one rectangle is contained inside another, as in Figure 3.

(Condition 3) The score obtained by making a connecting rectangle equals the number assigned to its pair of points.

Write a program that obtains the highest score while satisfying the above conditions.

Input

The first line contains the number of pairs.

The following lines give the coordinates of the two points in each pair, in order starting from pair $1$.

There are at most $50$ pairs ($100$ points). Each coordinate is a positive integer at most $100$.

The two points in a pair do not lie on the same vertical or horizontal line.

Output

On the first line, output the number of selected pairs. On the next line, output the numbers of the selected connecting rectangles in increasing order.

Examples

Input 1

6
2 5 1 3
5 6 3 2
5 2 6 4
7 6 5 8
1 6 5 4
3 7 7 3

Output 1

3
1 3 4