{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/1kgx165m.png)"},{"iden":"statement","content":"给定 $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$。\n\n你需要找出一个 $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$。\n\n$M$ 是给定的常数，$A\\oplus B$ 表示 $(A\\cup B)-(A\\cap B)$。"},{"iden":"input","content":"第一行两个整数 $n,m$；\n\n接下来 $n$ 行每行两个整数表示 $x_i,y_i$；\n\n接下来 $m$ 行每行三个整数表示 $A_j,B_j,C_j$。"},{"iden":"output","content":"输出 $m$ 行，依次表示 $p_1,\\dots,p_m$。"},{"iden":"note","content":"Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078\n\n对于 $100\\%$ 的数据，满足\n\n$1\\le n\\le 10^5$\n\n$1\\le m\\le 2\\times 10^5$\n\n$M=1.8\\times 10^8$\n\n$A_j^2+B_j^2>0$\n\n$-10^8\\le x_i,y_i,A_j,B_j,C_j\\le 10^8$。\n\n实际上数据是随机生成的。"}],"translated_statement":null,"sample_group":[["5 3\n2021 700\n-9384 1031\n2201 2561\n4982 6255\n-1700 388\n-2151 1808 -4359815\n-2850 -1980 7147359\n-924 217 -8902828","2\n1\n3"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}