Tasossa on $n$ pistettä $P_1, P_2, \ldots, P_n$. VegiCatilla on sinulle $q$ kyselyä. Jokainen kysely antaa pisteen $P$.

Muodosta jokaiselle kyselylle yksinkertainen monikulmio käyttäen joitakin annetuista pisteistä sen kärkinä. Monikulmion täytyy sisältää piste $P$ aidosti sisällään ja siinä täytyy olla pienin mahdollinen määrä kärkiä. Jos tällaista monikulmiota ei ole olemassa, tulosta $-1$.

Yksinkertainen monikulmio on suljettu murtoviiva, jossa on vähintään kolme eri kärkeä. Vierekkäiset sivut leikkaavat vain yhteisessä päätepisteessään, eivätkä ei-vierekkäiset sivut leikkaa toisiaan.

Esimerkkejä yksinkertaisista ja ei-yksinkertaisista monikulmioista

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 2 \cdot 10^4$), testitapausten lukumäärän. Seuraavaksi tulee testitapausten kuvaus.

Jokaisen testitapauksen ensimmäinen rivi sisältää kaksi positiivista kokonaislukua $n$ ja $q$ ($3 \le n \le 10^5$, $1 \le q \le 10^5$), jotka kuvaavat annettujen pisteiden lukumäärää ja kyselyiden lukumäärää.

Seuraavien $n$ rivin $i$:s rivi sisältää kaksi kokonaislukua $x_i$ ja $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), pisteen $P_i$ koordinaatit. On taattu, että nämä $n$ pistettä ovat pareittain eri pisteitä.

Jokainen seuraavista $q$ rivistä sisältää kaksi kokonaislukua $x$ ja $y$ ($-10^9 \le x, y \le 10^9$), kysytyn pisteen koordinaatit.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$.

On taattu, että lukujen $q$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$.

Tuloste

Tulosta jokaista kyselyä kohden omalle rivilleen yksi kokonaisluku $-1$, jos vaatimukset täyttävää monikulmiota ei ole olemassa.

Muussa tapauksessa tulosta monikulmio, jossa on pienin mahdollinen määrä kärkiä. Tulosta ensimmäiselle riville yksi kokonaisluku $m$, kärkien lukumäärä.

Tulosta toiselle riville $m$ kokonaislukua $a_1, a_2, \ldots, a_m$ ($1 \le a_i \le n$), kärkien indeksit järjestyksessä. Monikulmio on $P_{a_1} P_{a_2} \ldots P_{a_m}$. Kärjet voidaan tulostaa joko myötäpäivään tai vastapäivään.

Indeksien on oltava pareittain eri lukuja, ja tulostetun monikulmion on oltava yksinkertainen ja sisällettävä kysytty piste aidosti sisällään. Jos ratkaisuja on useita, tulosta mikä tahansa niistä.

Esimerkit

Syöte 1

2
5 1
0 4
-3 0
-3 -3
3 -3
3 0
0 0
3 1
0 4
-3 0
3 0
0 0

Tuloste 1

3
4 1 2
-1

Huomautus

Ensimmäisessä testitapauksessa kolmio $P_4 P_1 P_2$ sisältää kysytyn pisteen $P = (0, 0)$ aidosti sisällään. Koska monikulmiossa on vähintään kolme kärkeä, tässä kolmiossa on pienin mahdollinen määrä kärkiä.

Toisessa testitapauksessa ainoa mahdollinen monikulmio on kolmio $P_1 P_2 P_3$. Kysytty piste $P = (0, 0)$ sijaitsee sivulla $P_2 P_3$, joten vastaus on $-1$.

Kuvitukset esimerkkitestitapauksista