ישנן $n$ נקודות $P_1, P_2, \ldots, P_n$ במישור. ל-VegiCat יש $q$ שאילתות עבורך. כל שאילתה נותנת נקודה $P$.

עבור כל שאילתה, בנו מצולע פשוט המשתמש בחלק מהנקודות הנתונות כקודקודיו. המצולע חייב להכיל את $P$ ממש בתוכו, ולהיות בעל מספר הקודקודים המינימלי. אם לא קיים מצולע כזה, הדפיסו $-1$.

מצולע פשוט הוא קו שבור סגור עם לפחות שלושה קודקודים שונים. צלעות סמוכות נחתכות רק בנקודת הקצה המשותפת שלהן, וצלעות שאינן סמוכות אינן נחתכות.

דוגמאות למצולעים פשוטים ולא פשוטים

קלט

השורה הראשונה מכילה מספר שלם $T$ ($1 \le T \le 2 \cdot 10^4$), מספר מקרי הבדיקה. אחריה מופיע תיאור מקרי הבדיקה.

השורה הראשונה של כל מקרה בדיקה מכילה שני מספרים שלמים חיוביים $n$ ו-$q$ ($3 \le n \le 10^5$, $1 \le q \le 10^5$), המייצגים את מספר הנקודות הנתונות ואת מספר השאילתות.

השורה ה-$i$ מבין $n$ השורות הבאות מכילה שני מספרים שלמים $x_i$ ו-$y_i$ ($-10^9 \le x_i, y_i \le 10^9$), הקואורדינטות של $P_i$. מובטח כי $n$ הנקודות הללו שונות זו מזו.

כל אחת מ-$q$ השורות הבאות מכילה שני מספרים שלמים $x$ ו-$y$ ($-10^9 \le x, y \le 10^9$), הקואורדינטות של הנקודה הנשאלת.

מובטח כי סכום ערכי $n$ על פני כל מקרי הבדיקה אינו עולה על $10^5$.

מובטח כי סכום ערכי $q$ על פני כל מקרי הבדיקה אינו עולה על $10^5$.

פלט

עבור כל שאילתה, אם לא קיים מצולע המקיים את הדרישות, הדפיסו מספר שלם אחד $-1$ בשורה נפרדת.

אחרת, הדפיסו מצולע עם מספר הקודקודים המינימלי. בשורה הראשונה הדפיסו מספר שלם אחד $m$, מספר הקודקודים.

בשורה השנייה הדפיסו $m$ מספרים שלמים $a_1, a_2, \ldots, a_m$ ($1 \le a_i \le n$), אינדקסי הקודקודים לפי הסדר. המצולע הוא $P_{a_1} P_{a_2} \ldots P_{a_m}$. ניתן להדפיס את הקודקודים עם כיוון השעון או נגד כיוון השעון.

האינדקסים חייבים להיות שונים זה מזה, והמצולע המודפס חייב להיות פשוט ולהכיל את הנקודה הנשאלת ממש בתוכו. אם ישנם מספר פתרונות, הדפיסו אחד מהם.

דוגמאות

קלט 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

פלט 1

3
4 1 2
-1

הערה

במקרה הבדיקה הראשון, המשולש $P_4 P_1 P_2$ מכיל את הנקודה הנשאלת $P = (0, 0)$ ממש בתוכו. מכיוון שלמצולע יש לפחות שלושה קודקודים, למשולש זה יש את מספר הקודקודים המינימלי.

במקרה הבדיקה השני, המצולע האפשרי היחיד הוא המשולש $P_1 P_2 P_3$. הנקודה הנשאלת $P = (0, 0)$ נמצאת על הצלע $P_2 P_3$, ולכן התשובה היא $-1$.

איורים של מקרי הבדיקה בדוגמה