## TLE '17 Contest 2 P3 - Willson and Migration

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M
Author:

Problem type

Willson and his family migrating.

Willson the Canada Goose is like any other Canada goose - he migrates south for winter. As anyone knows, geese like to travel with their families.

Today, Willson is migrating with his family. There happen to be families of migrating geese, numbered from to . Willson's family is family . The family's journey can be represented by a ray starting at point and heading toward the point . Note that families do not stop upon reaching their heading point. It is guaranteed that the starting and heading points are distinct. Each family begins flight at the same time and flies at a speed of units per second, indefinitely.

However, when families collide, some geese might accidentally follow the wrong family. Willson wants to ensure that his family will remain together. Please tell him which other families of geese might come within units of his family during the flight.

#### Constraints

for all .

for all .

For of the points, for all .

For an additional of the points, either or for all .

#### Input Specification

The first line of input will contain two integers: , the number of families of geese, and .

lines of input follow. The line will contain five integers: .

#### Output Specification

Output, on separate lines and in order, the families that come within units of Willson's family. If there are no such families, do not output anything.

#### Sample Input

5 5
0 0 1 1 10
-4 -5 0 -1 9
10 4 9 4 2
100 200 101 100 7
2 6 0 6 24

#### Sample Output

3
4