無限に広がる二次元平面があります。

この二次元平面上には $N$ 個の「エモスポット」が存在し、$1, \dots, N$ の番号が付けられています。$i$ 番のエモスポットは点 $(x_i, y_i)$ を中心とする半径 $r_i$ の円 $C_i$ で表されます。なお、エモスポット同士は接することはありますが、共通部分が正の面積を持つことはありません。すなわち、任意の相異なる $i, j \ (1 \le i, j \le N)$ について、$C_i$ と $C_j$ は高々 $1$ つの交点しか持ちません。

Alice は二次元平面上の点 $(0, 0)$ に宿を建設しようと考えています。宿からはなるべく色んなエモスポットが見えると嬉しいので、Alice は点 $(0, 0)$ に宿を建設したときにどのエモスポットが宿から見ることができるかを知りたいです。

ここで、点 $(0, 0)$ から $i$ 番のエモスポットが見ることができるとは、他のどのエモスポットにもそのエモスポットの一部分あるいはすべてが隠されることがないことを指します。

より厳密には、次の条件を満たすことを指します。

$i$ 番のエモスポットを表す円内(円周上を含む)の任意の点と点 $(0, 0)$ を結ぶ線分の集合によって作られる領域を $S_i$ とする。

$1 \le j \le N, j \ne i$ を満たす $j$ について、$S_i$ と $C_j$ の共通部分が正の面積を持たない。

Alice の代わりに、点 $(0,0)$ から見ることができるエモスポットの番号を求めてください。

Hard (200点)

• $1 \le N \le {10}^{5}$
• $-{10}^5 \le x_i, y_i \le {10}^{5}$
• $\left|x_i\right| + \left|y_i\right| \gt 1$
• $1 \le r_i \lt \sqrt{x_i^2 + y_i^2}$
• 任意の $2$ つのエモスポットは正の面積の共通部分を持たない
• 入力はすべて整数

Normal (75点)

• Hard の制約に以下の制約を追加
• $1 \le N \le 1000$
• $2 \le x_i \le 1000$
• $-1000 \le y_i \le 1000$
• $1 \le r_i \lt x_i$

Easy (75点)

• Hard の制約に以下の制約を追加
• $1 \le N \le 1000$
• $3 \le x_i \le 1000$
• $y_i \in \lbrace -x_i, 0, x_i \rbrace$
• $r_i = 1$

入力は以下の形式で標準入力から与えられます。

点 $(0,0)$ から見ることができるエモスポットの番号を昇順に空白区切りで $1$ 行に出力してください。

より具体的には、点 $(0,0)$ から見ることができるエモスポットが $P_1$ 番 $, \dots, P_k$ 番の $k$ ヵ所 $(1 \le P_1 < \dots < P_k \le N)$ であるとき、次の形式で出力してください。