你们中有些人可能知道如何在图中找到最小割。你们中有些人可能也听说过最大割问题是 NP-完全的（更正式地说，判定是否存在权值至少为 $k$ 的割的问题是 NP-完全的）。我敢打赌，你们中有些人甚至想过类似这样的事情：“嗯，如果我简单地将所有代价取反，把最大割问题转化为最小割问题会怎样？我的图灵奖和十亿美元在哪里……哦，糟糕，我明白了。”

事实证明，对于某些受限的图类，问题可能会比一般情况更容易。考虑平面最大割问题，其表述如下。考虑一个无向图 $G$，包含 $n$ 个顶点 $V = \{v_1, v_2, \dots, v_n\}$ 和 $m$ 条边 $E = \{(v_{a_1}, v_{b_1}), (v_{a_2}, v_{b_2}), \dots, (v_{a_m}, v_{b_m})\}$。该图是平面的，并且你已知其平面嵌入：除了图的描述外，你还知道顶点的坐标，使得如果我们绘制对应于图的边的线段，则没有两条边会共享内部点。此外，图的第 $j$ 条边还关联有一个整数代价 $c_j$。

你的任务是将图的顶点划分为两个不相交的集合 $A$ 和 $B$（$A \cup B = V$），使得割边的总代价尽可能大。如果一条边的两个端点中恰好有一个属于 $A$，另一个属于 $B$，则称该边为割边。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 200, 1 \le m \le 1000$)，分别表示图的顶点数和边数。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($-10^4 \le x_i, y_i \le 10^4$)，表示平面嵌入中第 $i$ 个顶点的坐标。没有两个点重合。

接下来的 $m$ 行中，第 $j$ 行包含三个整数 $a_j, b_j$ 和 $c_j$ ($1 \le a_j, b_j \le n, a_j \neq b_j, 0 \le c_j \le 10^5$)，表示第 $j$ 条边的端点及其关联的代价。

输出格式

第一行输出割边的最大可能总代价。

第二行输出 $n$ 个整数 $s_1, s_2, \dots, s_n$ ($s_i \in \{0, 1\}$)，其中如果 $i \in A$ 则 $s_i = 0$，如果 $i \in B$ 则 $s_i = 1$。如果有多种可能的答案，输出其中任意一个即可。

样例

样例输入 1

4 5
0 0
2 0
0 2
2 2
1 2 3
2 4 6
3 4 4
1 3 7
2 3 8

样例输出 1

21
0 0 1 1