题目背景

题目描述

给定 $n$ 个互不相同的点 $(x_i,y_i),\;1\le i\le n$，$m$ 个集合 $S_j=\{(x_i,y_i)\mid A_jx_i+B_jy_i+C_j>0\},\;1\le j\le m$。

你需要找出一个 $1,2,\dots,m$ 的排列 $p_1,\dots,p_m$，使得 $|S_{p_1}|+\sum\limits_{i=2}^m |S_{p_i}\oplus S_{p_{i-1}}|\le M$。

$M$ 是给定的常数，$A\oplus B$ 表示 $(A\cup B)-(A\cap B)$。

输入格式

第一行两个整数 $n,m$；

接下来 $n$ 行每行两个整数表示 $x_i,y_i$；

接下来 $m$ 行每行三个整数表示 $A_j,B_j,C_j$。

输出格式

输出 $m$ 行，依次表示 $p_1,\dots,p_m$。

5 3
2021 700
-9384 1031
2201 2561
4982 6255
-1700 388
-2151 1808 -4359815
-2850 -1980 7147359
-924 217 -8902828

2
1
3

提示

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足

$1\le n\le 10^5$

$1\le m\le 2\times 10^5$

$M=1.8\times 10^8$

$A_j^2+B_j^2>0$

$-10^8\le x_i,y_i,A_j,B_j,C_j\le 10^8$。