Problem G. Grand Theft Auto Wheel

Author:ACM ICPC 2009-2010, NEERC, Northern Subregional Contest   Time limit:3 sec
Input file:gtaw.in   Memory limit:256 Mb
Output file:gtaw.out  

Statement

Tommy is a wheel thief. His job was formerly as easy as pie: you lift a car, turn off wheel bolts, take the wheel and run away. But now everybody uses "anti-theft" bolts.

Anti-theft bolt is designed in such a way that it cannot be turned off with a usual wrench. Its head is a cylinder with a hole. To turn the anti-theft bolt off you need a right wrench. The wrench has a ring with a lug that exactly matches the shape of the bolt head.

Of course Tommy cannot get wrenches for all possible anti-theft bolts. But sometimes it is possible to turn off the bolt with the wrench that does not match it exactly.

More formally, the wrench can turn off the bolt if and only if two following conditions are satisfied:

Due to technical reasons, the shape of both — hole of the bolt head and lug of the wrench, are always a star-shaped polygons with theirs centers in the center of the bolt or wrench. So if it is described in polar coordinate system as a sequence of pairs (ri, ϕi) then ϕi + 1 < ϕi and ϕi + 1 − ϕi < 180.

Help Tommy do find out if it is possible to turn off the bolt with the wrenches he has.

Input file format

The first line of input file contains two integer numbers n and r — the number of wrenches and the radii of the bolt head and the wrenches' rings (1≤ n≤ 10, 1≤ R≤ 1000).

The following lines describe the bolt head. Description consists of an integer number m — number of vertices (3≤ m≤ 100) and m pairs of integer numbers (ri, ϕi) (1≤ ri < R; 0∘ ≤ ϕi < 360; ϕi < ϕi + 1; ϕi + 1 − ϕi < 180; ϕm − ϕ1 > 180).

The rest lines describe the wrenches in the same format.

Output file format

The first line of the output file must contain the number of wrenches that can be used to turn off the bolt. The following lines must contain wrench numbers in increasing order.

Sample tests

No. Input file (gtaw.in) Output file (gtaw.out)
1
3 10
4
9 0
9 90
9 180
9 270
4
8 45
8 135
8 225
8 315
4
6 45
6 135
6 225
6 315
3
7 0
7 90
6 225
2
1 3

0.066s 0.011s 15