직각 사슬 풀기

직각 사슬(rectilinear chain)은 수평 선분과 수직 선분이 번갈아 이어지는 순서열이다. 첫 선분은 원점 $(0,0)$에서 시작해 오른쪽으로 향한다. 선분이 $n$개인 직각 사슬은 $n$개의 순서쌍 $(l_k, t_k)$로 기술한다. $l_k$는 $k$번째 선분 $e_k$의 길이이고, $t_k$는 $e_k$에서 $e_{k+1}$로 꺾는 방향이다. $1 \le k < n$에서 왼쪽으로 꺾으면 $t_k = 1$, 오른쪽으로 꺾으면 $t_k = -1$이다. $k = n$일 때는 $e_n$이 마지막 선분임을 뜻하도록 $t_n = 0$으로 둔다. 예를 들어 그림 (a)의 사슬은 (4, 1), (5, -1), (2, -1), (2, -1), (4, 1), (5, 0)으로 기술된다.

그림. (a) 단순하지 않은 사슬. (b) 풀어낸 단순 사슬.

사슬이 단순하다는 것은 이웃한 두 선분이 공유하는 끝점을 빼면 어떤 두 선분도 점을 공유하지 않는다는 뜻이다. 그림 (a)의 사슬은 단순하지 않다. 꺾는 방향을 모두 그대로 두고 각 선분의 길이만 바꾸면 사슬을 풀어 단순하게 만들 수 있다. 풀어낸 사슬에서 각 선분의 길이는 $1$ 이상 $n$ 이하여야 한다. 그림 (b)는 (a)를 풀어낸 한 가지 결과이고, (4, 1), (5, -1), (2, -1), (2, -1), (1, 1), (2, 0)으로 기술된다.

푸는 방법은 보통 여러 가지다. 답을 하나로 정하려고 출력에서 설명하는 규칙으로 만든 사슬만 정답으로 인정한다.

첫 줄에 사슬의 선분 개수 $n$ ($1 \le n \le 10000$)이 주어진다. 이어지는 $n$개 줄 중 $k$번째 줄에는 $e_k$의 길이 $l_k$ ($1 \le l_k \le 10000$)와 꺾는 방향 $t_k$가 공백 하나를 사이에 두고 주어진다. $1 \le k < n$에서 $t_k$는 왼쪽으로 꺾으면 $1$, 오른쪽으로 꺾으면 $-1$이고, $t_n = 0$이다.

아래 규칙으로 만든 사슬의 선분 길이 $n$개를 입력 순서대로 한 줄에 공백 하나로 구분해 출력한다. 꺾는 방향은 입력과 같으므로 출력하지 않는다.

원점 $(0,0)$에서 시작하고, 처음에 방문한 점은 원점뿐이다. $k = 1$부터 $n$까지 차례로 $e_k$의 끝점을 다음과 같이 정한다. 여기서 방문한 점은 원점과 $e_1$부터 $e_{k-1}$까지의 끝점을 말한다.

• $e_k$가 오른쪽으로 가면 끝점의 x좌표는 방문한 점의 x좌표 중 최댓값보다 $1$ 크다.
• $e_k$가 왼쪽으로 가면 끝점의 x좌표는 방문한 점의 x좌표 중 최솟값보다 $1$ 작다.
• $e_k$가 위로 가면 끝점의 y좌표는 방문한 점의 y좌표 중 최댓값보다 $1$ 크다.
• $e_k$가 아래로 가면 끝점의 y좌표는 방문한 점의 y좌표 중 최솟값보다 $1$ 작다.

$e_k$의 길이는 시작점과 끝점 사이의 거리다. 이렇게 만든 사슬은 항상 단순하고 모든 길이가 $1$ 이상 $n$ 이하다. 입력으로 주어지는 길이 $l_k$는 이 규칙에 쓰이지 않는다.