Bajteaux 子爵拥有一批著名的巨石收藏。此前，他一直将这些巨石存放在宫殿的地下室中，但最近他决定将这些收藏品展示在他广阔的花园里。

花园呈矩形，边长为 $1\,000\,000\,000$ 个单位，且各边分别平行于东西和南北方向。对于每一块巨石，子爵都确定了其放置点的坐标（坐标即为到花园南侧和西侧的距离），并将这些坐标交给了仆人。不幸的是，他忘记告诉仆人坐标的顺序（即对于某些巨石，第一个坐标是所谓的“$y$ 坐标”，即纵坐标；而对于另一些巨石，第一个坐标是所谓的“$x$ 坐标”，即横坐标）。仆人们并不知道这一点，他们按照习惯的坐标顺序（即标准笛卡尔坐标系：先横坐标，即通常所说的“$x$ 坐标”）放置了这些巨石。

为了保护他的收藏，子爵决定用围栏将其围起来。出于美观考虑，围栏必须是一个边与花园各边平行的矩形。花园的布局已经规划好，使得围栏的总长度最小（即在所有可能的坐标顺序组合中，子爵原始的坐标顺序要求围栏长度最小——我们假设矩形的边长可以为零）。

仆人们必须移动这些巨石，使得所需的围栏长度最小，以免他们的错误变得显眼。每块巨石只能通过交换其坐标的方式进行移动，以保持其坐标集合不变。由于巨石很重，仆人们希望通过最小化被移动巨石的总重量来减少他们的工作量。

请编写一个程序：

• 读取巨石在花园中的当前位置及其各自的重量；
• 确定一个移动方案，在使保护巨石所需的围栏长度最小化的同时，也使被移动巨石的总重量最小化；
• 将结果输出到标准输出。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 1\,000\,000$)，表示收藏中巨石的数量。接下来的 $n$ 行，每行包含三个整数 $x_i, y_i$ 和 $m_i$ ($0 \le x_i, y_i \le 1\,000\,000\,000$, $1 \le m_i \le 2\,000$)，由空格分隔，分别表示第 $i$ 块巨石当前的坐标和重量。输入中不会出现重复的无序坐标对。

输出格式

第一行应包含两个整数，由空格分隔，分别表示可能的最小围栏长度以及为获得该长度所需移动的巨石的最小总重量。

第二行应包含一个由 $n$ 个 0 和/或 1 组成的序列，如果第 $i$ 块巨石在最优解中需要被移动，则序列的第 $i$ 个元素为 1，否则为 0。如果存在多个正确的解，输出其中任意一个即可。

样例

输入 1

5
2 3 400
1 4 100
2 2 655
3 4 100
5 3 277

输出 1

10 200
01010