直线链是一个交替出现水平和垂直线段的有序序列，如图 K.1 所示。给定一个直线链，其第一条线段从原点 $(0, 0)$ 出发并向右延伸。这样的 $n$ 条边的直线链可以描述为 $n$ 个二元组 $(l_k, t_k)$ 的序列，其中 $l_k$ 是第 $k$ 条边 $e_k$ 的长度，$t_k$ 表示从第 $k$ 条边 $e_k$ 到第 $k+1$ 条边 $e_{k+1}$ 的转向。对于 $1 \le k < n$，如果链从 $e_k$ 到 $e_{k+1}$ 向左转，则 $t_k = 1$；如果向右转，则 $t_k = -1$。对于 $k = n$，$t_k$ 被设为 $0$，表示 $e_k$ 是链的最后一条边。例如，图 K.1(a) 中所示的六条边的直线链描述为序列 $(4, 1), (5, -1), (2, -1), (2, -1), (4, 1), (5, 0)$。

图 K.1. (a) 非简单链。(b) 解开后的简单链

你可能已经注意到，根据上述描述绘制的直线链并不简单。如果链中任意两条边除了在端点处共享外没有其他交点，则称该链是简单的。为了以更简洁的方式表示链，如果它不是简单的，你希望通过修改其边的长度使其变得简单。换句话说，你需要通过修改边的长度将给定的直线链转换为一条简单链。但结果链中每条边的长度必须至少为 $1$ 且最多为 $n$，且转向必须保持不变。图 K.1(b) 展示了图 K.1(a) 中非简单链的一种可能的修改方式，其描述为 $(4, 1), (5, -1), (2, -1), (2, -1), (1, 1), (2, 0)$。

给定一个直线链的描述，请编写一个程序来解开该直线链。

输入格式

程序从标准输入读取数据。第一行包含一个整数 $n$ ($1 \le n \le 10,000$)，表示输入直线链的边数。接下来的 $n$ 行中，第 $k$ 行包含两个整数 $l_k$ 和 $t_k$，由空格分隔，其中 $l_k$ ($1 \le l_k \le 10,000$) 是边 $e_k$ 的长度，$t_k$ 是从 $e_k$ 到 $e_{k+1}$ 的转向，$t_k = 1$ 表示左转，$t_k = -1$ 表示右转，对于 $k = n$，$t_k = 0$。

输出格式

程序将结果输出到标准输出。第一行应包含 $n$ 个正整数，表示根据输入链的边顺序，解开后的简单链的边长。每条边的长度应至少为 $1$ 且最多为 $n$。注意，你不需要输出转向，因为简单链的转向与输入链的转向相同。你可以假设输入中描述的任何直线链都可以通过满足边长条件的方案解开。

样例

样例输入 1

6
4 1
5 -1
2 -1
2 -1
4 1
5 0

样例输出 1

4 5 2 2 1 2

样例输入 2

6
3 1
3 1
2 1
4 1
1 1
3 0

样例输出 2

2 3 2 2 1 1