Жазықтықта $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$) берілген.

Келесі $n$ жолдың $i$-шісінде $P_i$ нүктесінің координаттарын білдіретін екі бүтін сан $x_i$ және $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) берілген. Осы $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$.

Мысалдағы тест жағдайларының иллюстрациялары