Problem F
Endless Turning

Picture by Cha già José via Flickr

Last week your little sister celebrated her birthday, and she was very pleased with her birthday present: a brand new scooter! Since then several times a day she goes for a drive, without telling anyone. She will leave the house, and go right on the pavement along the road. Fortunately she knows that she is not allowed to cross the road, and she is not sufficiently skilful with her new toy to turn around on the pavement. This means that, in order to continue her way, at each intersection she must turn right.

Every time your sister sets out, you are sent after her, of which you grow tired. Thus, knowing your little sister’s ways with her scooter, you decide to write a program to find her.

The city consists of $R$ roads. Each road has a name which does not contain any spaces, and is an infinite line in the Euclidean plane. No three roads go through one point, i.e. at every intersection exactly two roads intersect. You figured out that your sister by this time should have completed $N$ turns on the intersections of the city, unless of course she managed to leave the city by travelling on a road in a direction in which there is no other intersection, in which case she might not be able to even complete $N$ turns. Your task is to write a program that tells you on which road your sister is right now.

Figure 1: Illustration of sample testcase 1 and 2

Input

The first line contains four integers: the number of roads $R$, the number of turns $N$ and the $X$- and $Y$-coordinate of your parents’ home, satisfying $R \leq 100$, $N \leq 10^{10}$ and $|X|,|Y| \leq 10^7$.

The next $R$ lines each describe a street. Each line contains one string $S$ (without spaces, containing only alphanumeric characters, of length at most $20$), the name of the street, and four integers $X_1, Y_1, X_2$, and $Y_2$, satisfying $|X_1|,|X_2|,|Y_1|,|Y_2| \leq 10^7$ and $(X_1,Y_1) \neq (X_2,Y_2)$, indicating that road $S$ goes through points $(X_1, Y_1)$ and $(X_2, Y_2)$.

The location of your parents’ home $(X,Y)$ is guaranteed to lie on a unique non-vertical street (i.e. not on an intersection), on the south (negative $Y$-direction) side of the street, meaning that your little sister will depart in the east (positive $X$) direction. Moreover, each intersection is guaranteed to have coordinates of absolute value at most $10^7$, and is guaranteed to lie at least $10^{-4}$ from each other intersection in the same street.

Output

Output a single line containing the name of the road where your little sister can be found.

3 4 1 1
Broadway 0 0 0 1
Narrowlane 0 0 1 0
Homedrive 1 1 2 0

Narrowlane

3 4 1 0
Broadway 0 0 0 1
Narrowlane 0 0 1 0
Homedrive 1 1 2 0

Homedrive