Problem Description

After continuous promotion over several years, the game of Risk has become immensely popular across the nation, serving as an important form of entertainment that is widely cherished by the public. Risk can be understood as a simplified strategy game where the objective is to conquer all territories. According to the rules, two countries are considered to have the potential for conflict if they are adjacent. We are interested in determining which countries have the potential for conflict in the current situation. Note that adjacency is defined by shared borders, and if two countries only share a point, they are not considered adjacent.

Each country's border is described by a series of line segments, ensuring that the border forms a simple polygon, meaning it does not intersect itself. To locate each country, we also provide the coordinates of the most powerful army of each country, ensuring that this point lies within one of the country's borders and not on the border itself.

Input Format

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 borders, respectively. \( 1 \leq n \leq 600 \) and \( 1 \leq m \leq 4000 \). The next \( n \) lines each contain a pair of numbers describing the coordinates of a country's main army. The following \( m \) lines each contain four numbers \( x1, y1, x2, y2 \), describing a border line segment from \( (x1, y1) \) to \( (x2, y2) \). All coordinates are integers between 0 and 10000.

It is guaranteed that the input segments intersect only at their endpoints. There is exactly one infinite blank area on the map that does not belong to any country. Each border line segment separates areas that either belong to two different countries or separate a country from the infinite blank area. This means that the areas on both sides of a border line segment do not belong to the same country or are both blank areas. Each enclosed area contains exactly one main army, indicating its ownership.

Output Format

The output file contains \( n \) lines. Each line starts with a number \( x \) indicating the number of countries that potentially conflict with this country, followed by \( x \) integers in ascending order, representing the identifiers of the potentially conflicting countries. Countries are numbered from 1 to \( n \) in the order they appear in the input. Note that numbers should be strictly separated by a single space and no trailing spaces should be output at the end of the line.

Sample Input and Output

Sample 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

Sample Output #1

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

Sample 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

Sample Output #2

1 2
2 1 3
2 2 4
1 3

见题面 Input 部分

见题面 Output 部分