Það eru $n$ punktar $P_1, P_2, \ldots, P_n$ í sléttunni. VegiCat er með $q$ fyrirspurnir handa þér. Hver fyrirspurn gefur punkt $P$.

Fyrir hverja fyrirspurn skal smíða einfaldan marghyrning með því að nota suma af gefnu punktunum sem hornpunkta hans. Marghyrningurinn verður að innihalda $P$ strangt inni í sér og hafa lágmarksfjölda hornpunkta. Ef enginn slíkur marghyrningur er til skal prenta $-1$.

Einfaldur marghyrningur er lokaður brotinn ferill með að minnsta kosti þremur ólíkum hornpunktum. Aðliggjandi brúnir skerast aðeins í sameiginlegum endapunkti sínum og óaðliggjandi brúnir skerast ekki.

Dæmi um einfalda og óeinfalda marghyrninga

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 2 \cdot 10^4$), fjölda prófunartilfella. Lýsing á prófunartilfellunum fylgir.

Fyrsta línan í hverju prófunartilfelli inniheldur tvær jákvæðar heiltölur $n$ og $q$ ($3 \le n \le 10^5$, $1 \le q \le 10^5$), sem tákna fjölda gefinna punkta og fjölda fyrirspurna.

$i$-ta línan af næstu $n$ línum inniheldur tvær heiltölur $x_i$ og $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), hnit punktsins $P_i$. Tryggt er að þessir $n$ punktar séu innbyrðis ólíkir.

Hver af næstu $q$ línum inniheldur tvær heiltölur $x$ og $y$ ($-10^9 \le x, y \le 10^9$), hnit punktsins í fyrirspurninni.

Tryggt er að summa $n$ yfir öll prófunartilfelli fari ekki yfir $10^5$.

Tryggt er að summa $q$ yfir öll prófunartilfelli fari ekki yfir $10^5$.

Úttak

Fyrir hverja fyrirspurn, ef enginn marghyrningur sem uppfyllir skilyrðin er til, skal prenta eina heiltölu $-1$ á línu.

Annars skal prenta marghyrning með lágmarksfjölda hornpunkta. Á fyrstu línunni skal prenta eina heiltölu $m$, fjölda hornpunkta.

Á annarri línunni skal prenta $m$ heiltölur $a_1, a_2, \ldots, a_m$ ($1 \le a_i \le n$), vísa hornpunktanna í röð. Marghyrningurinn er $P_{a_1} P_{a_2} \ldots P_{a_m}$. Hægt er að prenta hornpunktana annaðhvort réttsælis eða rangsælis.

Vísarnir verða að vera innbyrðis ólíkir og marghyrningurinn sem prentaður er verður að vera einfaldur og innihalda punktinn í fyrirspurninni strangt inni í sér. Ef fleiri en ein lausn er til má prenta hvaða lausn sem er.

Dæmi

Inntak 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

Úttak 1

3
4 1 2
-1

Athugasemd

Í fyrsta prófunartilfellinu inniheldur þríhyrningurinn $P_4 P_1 P_2$ punktinn í fyrirspurninni $P = (0, 0)$ strangt inni í sér. Þar sem marghyrningur hefur að minnsta kosti þrjá hornpunkta hefur þessi þríhyrningur lágmarksfjölda hornpunkta.

Í öðru prófunartilfellinu er eini mögulegi marghyrningurinn þríhyrningurinn $P_1 P_2 P_3$. Punkturinn í fyrirspurninni $P = (0, 0)$ liggur á brúninni $P_2 P_3$, svo svarið er $-1$.

Skýringarmyndir af prófunartilfellunum í dæminu