给定 n 个互不相同的点 (xi,yi),m 个集合 Sj={(xi,yi)∣Ajxi+Bjyi+Cj>0},你需要找出一个 1,2,⋯,m 的排列 p1,p2,⋯,pm,使得 |Sp1|+∑mi=2|Spi⊕Spi−1|≤M,M 是给定的常数,A⊕B 表示 (A∪B)−(A∩B)。
输入格式
第一行两个整数 n,m;
接下来 n 行每行两个整数表示 xi,yi;
接下来 m 行每行三个整数表示 Aj,Bj,Cj。
输出格式
输出 m 行,依次表示 p1,p2,⋯,pm。
样例数据
样例 1 输入
5 5
1 1
4 5
1 4
1 9
1 9
1 2 3
4 5 6
7 8 9
1 1 4
5 1 4
样例 1 输出
1
2
3
4
5
样例 2~3
见下发文件。
子任务
注意,使用捆绑测试。
对于 20% 的数据,满足 1≤n≤104,1≤m≤104。
对于另外 30% 的数据,满足 xi=yi 或 xi=−yi。
对于 100% 的数据,满足 1≤n≤105,1≤m≤2×105,−109≤A,B,C,xi,yi≤109,M=1.8×108,所有输入均为整数。