Over the years, the game Risk has become popular across the country and is a widely enjoyed form of entertainment. Risk can be understood as a simple strategy game where the goal is to occupy all the land. According to the game rules, if two countries are adjacent, there is a possibility of conflict between them. We now wish to determine, given the current situation, which countries have the potential for conflict. Note that we consider two countries adjacent only if their borders share a common edge; if their territories only share a common point, they are not considered adjacent.

Each country's boundary consists of a series of line segments, and it is guaranteed that this boundary is a simple polygon, meaning it does not strictly self-intersect. To locate each country, we are also given the position of each country's largest army, and it is guaranteed that this position appears inside a certain shape, rather than on any boundary.

Input

The first line of the input file contains two integers $n$ and $m$, representing the number of countries on the map and the number of line segments describing the countries' boundaries, respectively. $1 \le n \le 600$, $1 \le m \le 4000$. The next $n$ lines each describe the coordinates of the main army of a country using a pair of numbers. The following $m$ lines each contain 4 numbers $x_1, y_1, x_2, y_2$, where $(x_1, y_1)-(x_2, y_2)$ describes a border line segment. All point coordinates are integers between $0$ and $10000$.

It is guaranteed that all input line segments intersect at most at their endpoints. There is exactly one infinite blank area on the map that does not belong to any country. The region on either side of each border line segment either belongs to two different countries or separates a country from that infinite blank area. That is, it is guaranteed that the regions on both sides of a border line segment do not both belong to the same country or both consist of the blank area. Every closed region contains exactly one main army, which represents the ownership of that region.

Input Explanation

Examples of valid and invalid input configurations

For example, the data in the first row of the image above is valid, while the data in the second row is invalid. The leftmost diagram in the second row shows a line segment where both sides are blank areas; the middle diagram shows a line segment where both sides belong to the same country; the rightmost diagram shows an army placed on a border line, which is illegal. Furthermore, if a region contains no army, it is also illegal. It is guaranteed that the input data provided is valid, and your program does not need to perform validation.

Output

The output file should contain $n$ lines. The first number $x$ on each line indicates that there are $x$ countries that may be in conflict with this country, followed by $x$ integers in ascending order on the same line, representing the IDs of the countries that may be in conflict with this country. Countries are numbered from $1$ to $n$ in the order they appear in the input. Note that numbers must be strictly separated by a single space, and do not output extra whitespace at the end of the line.

Examples

Input 1

4 12
3 2
11 8
12 17
1 19
0 0 10 0
10 0 20 0
20 0 20 10
20 10 20 20
20 20 10 20
10 20 0 20
0 20 0 10
0 10 0 0
10 0 10 10
0 10 10 10
20 10 10 10
10 20 10 10

Output 1

2 2 4
2 1 3
2 2 4
2 1 3

Input 2

4 16
170 13
24 88
152 49
110 130
60 60 140 60
140 60 140 140
140 140 60 140
60 140 60 60
0 0 200 0
200 0 200 200
200 200 0 200
0 200 0 0
40 40 160 40
160 40 160 160
160 160 40 160
40 160 40 40
20 20 180 20
180 20 180 180
180 180 20 180
20 180 20 20

Output 2

1 2
2 1 3
2 2 4
1 3