给定 $n$ 个互不相同的点 $(x_i, y_i)$，$m$ 个集合 $S_j = \{(x_i,y_i) \mid A_jx_i + B_jy_i + C_j > 0\}$，你需要找出一个 $1,2,\cdots, m$ 的排列 $p_1,p_2,\cdots,p_m$，使得 $|S_{p_1}| + \sum_{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,p_2,\cdots,p_m$。

样例数据

样例 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 \le n \le 10^4$，$1 \le m \le 10^4$。

对于另外 $30\%$ 的数据，满足 $x_i=y_i$ 或 $x_i = -y_i$。

对于 $100\%$ 的数据，满足 $1 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$，$-10^9 \le A,B,C,x_i,y_i \le 10^9$，$M=1.8 \times 10^8$，所有输入均为整数。