Helesta

题号：NC236508
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

You are given $n$ points $(x_i,y_i),\;1\le i\le n$ and $m$ sets $S_j=\{(x_i,y_i)\mid A_jx_i+B_jy_i+C_j>0\}$ ( $1\le j\le m$ ). You need to find a permutation $p_1,\dots,p_m$ of $1, 2,\dots,m$ , such that $|S_{p_1}|+\sum\limits_{i=2}^m |S_{p_i}\oplus S_{p_{i-1}}|\le M$ , where $M=1.8\times 10^8$ is a given constant and $A\oplus B$ means $(A\cup B)-(A\cap B)$ .

If there are several possible answers, you can print any of them.

输入描述:

The first line contains two integers  ().

Each line in the next  lines contains two integers  ().

Each line in the next  lines contains three integers  ().

It is guaranteed that  for .

输出描述:

Print  lines. In the -th line, print a single integer .

示例1

输入

复制

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

输出

复制

2
1
3