bobo 有一棵包含 $n$ 个顶点的树。bobo 想要为每个顶点 $v$ 分配一个 $m$ 维向量 $\mathbf{p}(v)$，使得对于所有顶点 $a, b$，满足 $\text{dist}(a, b) = \langle \mathbf{p}(a), \mathbf{p}(b) \rangle$。

注意，$\text{dist}(a, b)$ 是顶点 $a$ 和 $b$ 之间最短路径的长度。对于两个向量 $\mathbf{u} = (u_1, u_2, \dots, u_m)$ 和 $\mathbf{v} = (v_1, v_2, \dots, v_m)$，$\langle \mathbf{u}, \mathbf{v} \rangle = \max\{|u_1 - v_1|, |u_2 - v_2|, \dots, |u_m - v_m|\}$。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 1000$)。 为了方便起见，顶点编号为 $1, 2, \dots, n$。 接下来的 $(n - 1)$ 行，每行包含 3 个整数 $a_i, b_i, c_i$，表示顶点 $a_i$ 和 $b_i$ 之间存在一条长度为 $c_i$ 的边 ($1 \le a_i, b_i \le n, 1 \le c_i \le 100000$)。

输出格式

第一行包含一个整数 $m$，表示向量的维度 ($1 \le m \le 16$)。 接下来的 $n$ 行，每行包含 $m$ 个整数，表示向量 $\mathbf{p}(i)$。坐标范围应在 $[-10^9, 10^9]$ 之间。

任何符合要求的解都将被接受。

样例

样例输入 1

2
1 2 2

样例输出 1

1
0
-2

样例输入 2

4
1 2 1
1 3 1
1 4 1

样例输出 2

2
0 0
-1 -1
-1 1
1 1