在遥远的未来，人类发现了一颗巨大、温暖且郁郁葱葱的行星以供殖民，并正在建造许多发电厂来支持新的殖民地。令人惊叹的技术使建造者能够利用宇宙的巨大能量。然而，他们忽略了一个小事实：将两座发电厂建得太近会产生巨大的连锁反应风险，这反过来会导致壮观的爆炸。显然，这是应该避免的。

幸运的是，发电厂可以使用两种能量，分别称为“光”能量和“暗”能量，它们之间不会相互作用。如果一些发电厂使用光能量，另一些使用暗能量，那么相同类型发电厂之间的距离可能会比以前更大，这将使整个工程的危险性降低。

任务

给定 $n$ 座发电厂的位置（行星足够大，我们可以将它们视为平面上的点），为每座发电厂分配光能量或暗能量，使得相同类型发电厂之间的欧几里得距离尽可能大。为了避免输出实数，请输出该最大距离的平方，以及将发电厂划分为“光”和“暗”两组的方案。

输入格式

第一行包含一个整数 $N$ ($3 \le N \le 100\,000$)，表示发电厂的数量。接下来的 $N$ 行中，第 $i$ 行包含两个整数 $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$)，表示第 $i$ 座发电厂的坐标。所有点互不相同。

输出格式

第一行输出一个整数，表示所能达到的最大距离的平方。 第二行包含使用光能量的发电厂数量，第三行包含这些发电厂的编号（以空格分隔）。 第四行和第五行以相同的格式描述使用暗能量的发电厂。 如果存在多种有效的解决方案，输出其中任意一种即可。

子任务

样例

样例输入 1

4
0 3
0 0
3 0
3 3

样例输出 1

18
2
1 3
2
2 4