Maija on saanut syntymäpäivälahjakseen upouuden potkulaudan. Innoissaan uudesta lelustaan hän on päättänyt lähteä kokeilemaan sitä. Maija lähtee kotoaan ja kääntyy oikealle kotinsa edessä olevalle jalkakäytävälle. Maija on vielä niin nuori, ettei hän saa ylittää teitä, joten hän kääntyy jokaisesta risteyksestä oikealle. Lisäksi hän ei vielä hallitse potkulautaansa niin hyvin että voisi vaihtaa suuntaansa jalkakäytävällä.

Uolevi on huolissaan pikkusiskostaan ja haluaa löytää hänet. Auta Uolevia selvittämään, millä tiellä Maija on, kun hän on kääntynyt $N$ kertaa, tai mitä tietä pitkin hän poistuu kaupungista jos vastaan ei tule enää risteyksiä.

Maijan ja Uolevin kotikaupunki muodostuu $R$ äärettömän pitkästä suorasta tiestä, joista jokaisella on nimi. Mitkään kolme tietä eivät risteä samassa pisteessä.

Syöte

Syötteen ensimmäisellä rivillä on teiden määrä $R$, Maijan tekemien käännösten määrä $N$ sekä Maijan ja Uolevin kodin $X$- ja $Y$-koordinaatti.

Jokainen seuraavista $R$ rivistä kuvaa yhden tien. Rivillä on tien nimi $S$ (vain aakkosia ja numeroita, ei välejä), ja neljä kokonaislukua $X_1$, $Y_1$, $X_2$ ja $Y_2$. Tie kulkee näiden pisteiden kautta.

Maijan ja Uolevin koti sijaitsee yksiselitteisellä ei-pystysuoralla tiellä etelän puolella (negatiivinen $Y$-koordinaatti). Maija lähtee siis aina positiivisen $X$-akselin suuntaan.

Tuloste

Tulosta tien nimi, jolla Maija on $N$ käännöksen jälkeen, tai jota pitkin hän poistuu kaupungista jos vastaan ei tule enää risteyksiä.

Rajat

• $R \le 100$
• $|X|, |Y|, |X_1|, |Y_1|, |X_2|, |Y_2| \le 10^7$
• $N \le 10^{10}$

Jokaisen risteyksen koordinaattien itseisarvo on korkeintaan $10^7$, ja jokainen risteys on ainakin $10^{-4}$ päässä toisesta risteyksestä.

Esimerkki 1

Syöte:

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

Tuloste:

Narrowlane

Maija lähtee Homedriveä itään, kääntyy oikealle Narrowlanelle, Brodwaylle, Homedrivelle ja Narrowlanelle. Neljän käännöksen jälkeen hän on siis Narrowlanella.

Esimerkki 2

Syöte:

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

Tuloste:

Homedrive

Maila lähtee Narrowlanea itään ja kääntyy Homedrivelle, jonka jälkeen matkalle ei osu enää yhtään risteystä. Maija poistuu siis kaupungista Homedriveä pitkin.

Alkuperäinen tehtävä: BAPC 2016 F