你正在玩吃豆人游戏，并且被困在了一个关卡中：每次开始这个关卡，你很快就会被幽灵杀死。在这个特定版本的游戏中，幽灵只会在关卡开始 $T$ 秒后出现，而吃豆人可以以每秒 1 个单位的固定速度向任意方向移动。棋盘上有 $n$ 个樱桃，为了获胜，你必须收集至少一半的樱桃（不进行四舍五入！）。由于你唯一的麻烦是幽灵，你希望在不超过 $T$ 秒的时间内收集到所有需要的樱桃。

然而，由于你与游戏发明者岩谷彻（Mr. Toru Iwatani）先生相识，你从作者那里得知，设计上确实可以在不超过 $T$ 秒的时间内收集所有樱桃并回到起点！不过，你只需要收集其中一半的樱桃，且不需要回到起点。

你从点 $(0, 0)$ 出发。

输入格式

输入的第一行包含一个整数 $n$：棋盘上樱桃的数量（$1 \le n \le 5000$）。 接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$：第 $i$ 个樱桃的坐标。 输入的最后一行包含一个实数 $T$（$0 < T \le 10^{18}$，$T$ 小数点后最多包含 10 位数字）。所有坐标的绝对值不超过 $10^5$。保证在 $T - 10^{-3}$ 秒内收集所有樱桃并回到原点是可能的。

输出格式

输出 $\lceil \frac{n}{2} \rceil$ 个整数：你访问樱桃的顺序编号。樱桃的编号与输入中的顺序一致，从 1 到 $n$。

样例

输入 1

3
1 1
0 2
-1 1
5.66

输出 1

3 2