Treeland 的所有电影明星都聚集在首都参加电影学院奖颁奖典礼。这一次，组织者决定为欢迎环节准备一些全新的东西。他们的想法是用一块印有 Treeland 地图的地毯来代替传统的红地毯。

Treeland 由 $n$ 个城市和 $n - 1$ 条双向道路组成，使得从任意一个城市都可以到达其他任何城市。我们将地毯表示为一个 $1\,000\,000 \times 20$ 的单位正方形网格。城市应该绘制在某些网格单元的中心，且任意两个城市不能占用同一个单元格。之后，道路被绘制为连接相应单元格中心的线段。

为了使地毯美观，决定在放置城市时，使代表道路的任意两条线段都不相交。这意味着任意两条线段除了它们公共的端点之外，没有其他公共点。

某位聪明的数学家已经证明了解决方案的存在性，但遗憾的是，他的证明并没有给出构造答案的方法，因此这个任务被分配给了你。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 100\,000$) — Treeland 中的城市数量。

接下来的 $n - 1$ 行，每行包含一对整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) — 连接城市 $u_i$ 和 $v_i$ 的道路。保证可以从任意城市到达其他任何城市。

输出格式

输出 $n$ 行。其中第 $i$ 行应包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i \le 1\,000\,000$, $1 \le y_i \le 20$) — 放置第 $i$ 个城市的单元格坐标。

样例

输入样例 1

6
1 2
1 3
1 4
4 5
4 6

输出样例 1

2 2
1 1
1 3
3 2
4 3
4 1

输入样例 2

7
1 2
1 3
2 4
2 5
3 6
3 7

输出样例 2

1 1
1 2
2 2
1 3
2 3
3 3
4 3

说明

下图展示了第一个样例的一种可能解。