题目描述

Blue Mary 是一个有名的石头收藏家。迄今为止，他把他的藏品全部放在他的宫殿的地窖中。现在，他想将他的藏品陈列在他的花园中。皇家花园是一个边长为 $1000000000$ 单位的平行于坐标轴的正方形。

对于每个石头，Blue Mary 都有一个他想放置的坐标，然后将他告诉他的属下。不幸的是，他忘了告诉他们坐标的顺序（比如无法分辨 $(x,y)$ 和 $(y,x)$ ）。属下们，就自己决定了每个石头的具体位置。为了保护他的藏品，Blue Mary 决定建造一个篱笆来保护他们。

为了美学的需要，篱笆也被设计为平行于坐标轴的矩形。如果花园的布局知道了，那么就可以知道最短长度的篱笆的布局。他的属下们需要变换石头的坐标使得篱笆的长度最少。每个石头只能从 $(x,y)$ 变换为 $(y,x)$ ，由于每个石头的重量不一样。属下们希望他们移动的石头的重量和最少。

输入格式

第一行包含一个数 $n$ ，表示石头的数量（ $2 \le n \le 1000000$ ），接下来 $n$ 行分别描述 $n$ 个石头的初始坐标和重量 $x_i,y_i,m_i$。（ $0 \le x_i,y_i \le 1000000000，1 \le m_i \le 2000$ ）

输出格式

包含两行，第一行包含两个数由一个空格分割。最小的篱笆长度和最小的移动的石子的重量和。第二行为一个 01 字符串，第 $i$ 个字符为 $1$ 表示要改变第 $i$ 个石头的位置。$0$ 表示不改变。

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

10 200
01010

提示

题目来源

没有写明来源