Es gibt $n$ Punkte $P_1, P_2, \ldots, P_n$ in der Ebene. VegiCat hat $q$ Anfragen für dich. Jede Anfrage gibt einen Punkt $P$ vor.

Konstruiere für jede Anfrage ein einfaches Polygon, das einige der gegebenen Punkte als Eckpunkte verwendet. Das Polygon muss $P$ strikt in seinem Inneren enthalten und die minimale Anzahl von Eckpunkten besitzen. Falls kein solches Polygon existiert, gib $-1$ aus.

Ein einfaches Polygon ist ein geschlossener Polygonzug mit mindestens drei verschiedenen Eckpunkten. Benachbarte Kanten schneiden sich nur in ihrem gemeinsamen Endpunkt, und nicht benachbarte Kanten schneiden sich nicht.

Beispiele für einfache und nicht-einfache Polygone

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 2 \cdot 10^4$), die Anzahl der Testfälle. Die Beschreibung der Testfälle folgt.

Die erste Zeile jedes Testfalls enthält zwei positive ganze Zahlen $n$ und $q$ ($3 \le n \le 10^5$, $1 \le q \le 10^5$), die die Anzahl der gegebenen Punkte bzw. die Anzahl der Anfragen darstellen.

Die $i$-te der nächsten $n$ Zeilen enthält zwei ganze Zahlen $x_i$ und $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), die Koordinaten von $P_i$. Es wird garantiert, dass diese $n$ Punkte paarweise verschieden sind.

Jede der nächsten $q$ Zeilen enthält zwei ganze Zahlen $x$ und $y$ ($-10^9 \le x, y \le 10^9$), die Koordinaten des angefragten Punktes.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^5$ nicht überschreitet.

Es wird garantiert, dass die Summe von $q$ über alle Testfälle $10^5$ nicht überschreitet.

Ausgabe

Falls für eine Anfrage kein Polygon existiert, das die Anforderungen erfüllt, gib eine ganze Zahl $-1$ in einer eigenen Zeile aus.

Gib andernfalls ein Polygon mit der minimalen Anzahl von Eckpunkten aus. Gib in der ersten Zeile eine ganze Zahl $m$ aus, die Anzahl der Eckpunkte.

Gib in der zweiten Zeile $m$ ganze Zahlen $a_1, a_2, \ldots, a_m$ ($1 \le a_i \le n$) aus, die Indizes der Eckpunkte in ihrer Reihenfolge. Das Polygon ist $P_{a_1} P_{a_2} \ldots P_{a_m}$. Die Eckpunkte können entweder im Uhrzeigersinn oder gegen den Uhrzeigersinn ausgegeben werden.

Die Indizes müssen paarweise verschieden sein, und das ausgegebene Polygon muss einfach sein und den angefragten Punkt strikt im Inneren enthalten. Falls es mehrere Lösungen gibt, gib eine beliebige davon aus.

Beispiele

Eingabe 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

Ausgabe 1

3
4 1 2
-1

Hinweis

Im ersten Testfall enthält das Dreieck $P_4 P_1 P_2$ den angefragten Punkt $P = (0, 0)$ strikt in seinem Inneren. Da ein Polygon mindestens drei Eckpunkte hat, besitzt dieses Dreieck die minimale Anzahl von Eckpunkten.

Im zweiten Testfall ist das einzige mögliche Polygon das Dreieck $P_1 P_2 P_3$. Der angefragte Punkt $P = (0, 0)$ liegt auf der Kante $P_2 P_3$, daher lautet die Antwort $-1$.

Illustrationen der Beispiel-Testfälle