14961번 - Untangling Chain 스페셜 저지다국어

A rectilinear chain is an ordered sequence that alternates horizontal and vertical segments as in Figure K.1. You are given a rectilinear chain whose first segment starts from the origin (0,0) and goes to the right. Such a rectilinear chain of n edges can be described as a sequence of n pairs (l_k,t_k) where l_k is the length of the k-th edge e_k and t_k denotes the turning direction from the k-th edge e_k to the (k+1)-st edge e_k+1. For 1 ≤ k < n, if the chain turns left from e_k to e_k+1, then t_k = 1, and if it turns right, then t_k = -1. For k = n, t_k is set to be zero to indicate that e_k is the last edge of the chain. For example, a rectilinear chain of six pairs shown in Figure 1(a) is described as a sequence of six pairs (4, 1), (5, -1), (2, -1), (2, -1), (4, 1), (5, 0).

Figure K.1. (a) A non-simple chain. (b) An untangled simple chain

You would already notice that the rectilinear chain drawn by the given description is not simple. A chain is simple if any two edges in the chain have no intersection except at the end points shared by adjacent edges. To represent the chain in a more succinct way, you want to make it simple if it is not simple. In other words, you need to untangle a given rectilinear chain to a simple chain by modifying the length of its edges. But the length of each edge in the resulting chain must be at least 1 and at most n, and the turning directions must be kept unchanged. The chain shown in Figure K.1(b) shows one of possible modifications for the non-simple chain given in Figure K.1(a), and its description is (4, 1), (5, -1), (2, -1), (2, -1), (1, 1), (2, 0).

Given a description of a rectilinear chain, you should write a program to untangle the rectilinear chain.

Your program is to read from standard input. The first line contains an integer, n (1 ≤ n ≤ 10,000), representing the number of edges of an input rectilinear chain. In the following n lines, the k-th line contains two integers l_k and t_k for the edge e_k, separated by a single space, where l_k (1 ≤ l_k ≤ 10,000) is the length of e_k, and t_k is the turning direction from e_k to e_k+1; t_k =  1 if it is the left turn and t_k = -1 if it is the right turn for 1 ≤ k < n, and t_k = 0 for k = n.

Your program is to write to standard output. The first line should contain n positive integers, representing the length of the edges of your untangled simple chain according to the edge order of the input chain. Each length should be at least 1 and at most n. Note that you do not need to output the turning directions because the turning directions of the simple chain is identical to the ones of the input chain. You can assume that any rectilinear chain described in the input can be untangled with the edge length condition.