Given $n$ distinct points $(x_i, y_i)$ and $m$ sets $S_j = \{(x_i, y_i) \mid A_j x_i + B_j y_i + C_j > 0\}$, you need to find a permutation $p_1, p_2, \dots, p_m$ of $1, 2, \dots, m$ such that $|S_{p_1}| + \sum_{i=2}^m |S_{p_i} \oplus S_{p_{i-1}}| \le M$, where $M$ is a given constant and $A \oplus B$ denotes the symmetric difference $(A \cup B) - (A \cap B)$.

Input

The first line contains two integers $n$ and $m$.

The next $n$ lines each contain two integers representing $x_i$ and $y_i$.

The next $m$ lines each contain three integers representing $A_j$, $B_j$, and $C_j$.

Output

Output $m$ lines, representing $p_1, p_2, \dots, p_m$ in order.

Examples

Input 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

Output 1

1
2
3
4
5

Examples 2~3

See the provided files.

Subtasks

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078

Note: Bundled testing is used.

For $20\%$ of the data, $1 \le n \le 10^4$ and $1 \le m \le 10^4$.

For another $30\%$ of the data, $x_i = y_i$ or $x_i = -y_i$.

For $100\%$ of the data, $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$, and all inputs are integers.