Problem L
Sýndargirðing

Sýnidæmi 1, gert með GeoGebru

Ingfríður ákvað að taka þátt í Capture the Flag æfingu. Til að forðast að Ingfríður gæti stolið fánanum passaði Jörmunrekur að setja símkort inn í efnið á fánanum til að hann myndi alltaf vita hvar fáninn væri. En Ingfríður var einu skrefi á undan og vissi að hann hefði gert þetta.

Henni tókst að laumast að fánanum og skipta honum út fyrir gerviafrit, en nú er smá vandi. Til að Jörmunrekur fatti ekki að fáninn sé annar fáni þarf símkortið alltaf að fá rétta staðsetningu. Til þess þarf Ingfríður að fylgjast með hvert Jörmunrekur og lið hans fer með fánann og plata símkortið svo það haldi að það sé þar sem Jörmunrekur er.

Ingfríður er með afrit af kortinu sem símkort Jörmunreks notar, sem samanstendur af þríhyrningum. Nú þarf hún að vita, í hvaða þríhyrning er Jörmunrekur meðal þessara þríhyrninga?

Gefið er að þríhyrningar skarist ekki nema á köntunum og Jörmunrekur er ekki nákvæmlega á kantinum á neinum þríhyrningi, annað hvort alveg fyrir innan eða alveg fyrir utan.

Inntak

Fyrsta lína inntaksins inniheldur jákvæða heiltölu $0 \leq n \leq 1\, 000$, fjöldi þríhyrninga sem munu fylgja. Hver þríhyrningur er á einni línu.

Hver þríhyrningur samanstendur af sex hnitum $x_1, y_1, x_2, y_2, x_3, y_3$ aðskilin með bilum. Þetta táknar þríhyrninginn með hornpunkta $(x_1, y_1), (x_2, y_2)$ og $(x_3, y_3)$.

Loks kemur ein lína með tveimur hnitum $x, y$ aðskilin með bili. Þetta táknar að Jörmunrekur og fáninn sé staðsettur á hniti $(x, y)$.

Öll hnit í inntakinu eru heiltölur með algildi í mesta lagi $10^6$.

Úttak

Ef Jörmunrekur er í $i$-ta þríhyrningi inntaksins (fyrsti þríhyrningurinn er $0$-ti þríhyrningurinn), prentið $i$. Ef hann er í engum þríhyrninganna prentið í staðinn $-1$.

6
2 2 2 10 8 8
2 2 10 2 8 8
10 2 10 4 8 8
14 0 10 4 8 8
14 0 18 16 8 8
18 16 2 10 8 8
14 1

4

0
0 0

-1