给定 $n$ 个点 $(x_i, y_i)$，其中 $1 \le i \le n$，以及 $m$ 个集合 $S_j = \{(x_i, y_i) \mid A_j x_i + B_j y_i + C_j > 0\}$（$1 \le j \le m$）。

你需要找到一个 $1, 2, \dots, m$ 的排列 $p_1, \dots, p_m$，使得 $|S_{p_1}| + \sum_{i=2}^{m} |S_{p_i} \oplus S_{p_{i-1}}| \le M$，其中 $M = 1.8 \times 10^8$ 是给定的常数，$A \oplus B$ 表示对称差 $(A \cup B) - (A \cap B)$。

如果存在多个可能的答案，你可以输出其中任意一个。

输入格式

第一行包含两个整数 $n, m$（$1 \le n \le 10^5, 1 \le m \le 2 \times 10^5$）。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$（$-10^8 \le x_i, y_i \le 10^8$）。

接下来的 $m$ 行，每行包含三个整数 $A_j, B_j, C_j$（$-10^8 \le A_j, B_j, C_j \le 10^8$）。

保证对于 $1 \le j \le m$，满足 $A_j^2 + B_j^2 > 0$。

输出格式

输出 $m$ 行。在第 $i$ 行，输出一个整数 $p_i$。

样例

样例输入 1

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

样例输出 1

2
1
3