Untangling Chain

A rectilinear chain is an ordered sequence of segments that alternates between horizontal and vertical. Its first segment starts at the origin $(0,0)$ and goes to the right. A rectilinear chain of $n$ edges is described by $n$ pairs $(l_k, t_k)$, where $l_k$ is the length of the $k$-th edge $e_k$ and $t_k$ is the turning direction from $e_k$ to $e_{k+1}$. For $1 \le k < n$, $t_k = 1$ if the chain turns left and $t_k = -1$ if it turns right. For $k = n$, $t_n = 0$ marks $e_n$ as the last edge. For example, the chain in figure (a) is described by (4, 1), (5, -1), (2, -1), (2, -1), (4, 1), (5, 0).

Figure. (a) A chain that is not simple. (b) An untangled simple chain.

A chain is simple if no two of its edges share a point, apart from the endpoint that two adjacent edges share. The chain in figure (a) is not simple. Keeping every turning direction and changing only the length of each edge untangles the chain into a simple one. In the untangled chain each length must be between $1$ and $n$. Figure (b) shows one untangling of (a), described by (4, 1), (5, -1), (2, -1), (2, -1), (1, 1), (2, 0).

A chain usually has many untanglings. To pin the answer down to one, only the chain built by the rule in the output section counts as correct.

The first line contains an integer $n$ ($1 \le n \le 10000$), the number of edges of the chain. Each of the next $n$ lines contains two integers separated by a single space: the length $l_k$ of $e_k$ ($1 \le l_k \le 10000$) and the turning direction $t_k$ from $e_k$ to $e_{k+1}$. For $1 \le k < n$, $t_k$ is $1$ for a left turn and $-1$ for a right turn, and $t_n = 0$.

Print the $n$ edge lengths of the chain built by the rule below, in the input order, on one line separated by single spaces. The turning directions match the input, so do not print them.

Start at the origin $(0,0)$, which is the only visited point at the beginning. For $k = 1$ up to $n$ in order, fix the endpoint of $e_k$ as follows. The visited points are the origin together with the endpoints of $e_1$ through $e_{k-1}$.

• If $e_k$ goes right, the x coordinate of its endpoint is $1$ more than the largest x coordinate among the visited points.
• If $e_k$ goes left, the x coordinate of its endpoint is $1$ less than the smallest x coordinate among the visited points.
• If $e_k$ goes up, the y coordinate of its endpoint is $1$ more than the largest y coordinate among the visited points.
• If $e_k$ goes down, the y coordinate of its endpoint is $1$ less than the smallest y coordinate among the visited points.

The length of $e_k$ is the distance between its start point and its endpoint. The chain built this way is always simple, and every length is between $1$ and $n$. The rule does not use the lengths $l_k$ given in the input.