### IOI '02 - Yong-In, Korea

## Utopia Divided

The beautiful land of Utopia was once ravaged by war. When the hostilities subsided the country was divided into four regions by a longitude (north-south line) and a latitude (east-west line). The intersection of these lines became known as the point (0,0). All four parts claimed the name Utopia, but as time went by they generally became known as Utopia 1 (northeast), 2 (northwest), 3 (southwest) and 4 (southeast). A point in any of the regions was identified by its distance east and its distance north of (0,0). These distances could be negative; hence a point in Utopia 2 was designated by a (negative, positive) pair, in Utopia 3 by a (negative, negative) pair, in Utopia 4 by (positive, negative) and in Utopia 1 by a pair of positive numbers.

A major problem was that citizens were not permitted to cross borders.
Fortunately, some ingenious IOI contestants from Utopia developed a safe means
of teleportation. The machine requires code numbers, each of which can only be
used once. Now the challenge facing the team, and you, is to guide the
teleporter from its initial position of (0,0) to the regions of Utopia in the
order requested. You don't care where in a region you land, but you will have a
sequence of *N* region numbers that specify the regions in which the
teleporter is to land. You may be asked to land in the same region in two or
more consecutive stops. After leaving the initial (0,0) point, you must never
land on a border.

You will receive as input a sequence of 2*N* code numbers and are to
write them as a sequence of *N* code pairs, placing a plus or a minus sign
before each number. If you are currently at the point (*x*,*y*) and
use the code pair (+*u*,-*v*), you will be teleported to the point
(*x*+*u*, *y*-*v*). You have the 2*N* numbers, and you
can use them in any order you like, each with a plus or a minus sign.

Suppose you have code numbers 7, 5, 6, 1, 3, 2, 4, 8 and are to guide the teleporter according to the sequence of region numbers 4, 1, 2 ,1. The sequence of code pairs (+7,-1), (-5,+2), (-4,+3), (+8,+6) achieves this as it teleports you from (0,0) to the locations (7,-1), (2,1), (-2,4) and (6,10) in that order. These points are located in Utopia 4, Utopia 1, Utopia 2, and Utopia 1, respectively.

You are given 2*N* distinct code numbers and a sequence of *N*
region numbers indicating where the teleporter is to land. Construct a sequence
of code pairs from the given numbers that guide the teleporter to go through
the given region sequence.

### Input

Your program is to read from standard input. The first line contains a
positive integer *N* (1 ≤ *N* ≤ 10000). The second line
contains the 2*N* distinct integer code numbers (1 ≤ *code number*
≤ 100000) separated by single spaces. The last line contains a sequence of
*N* region numbers, each of which is 1, 2, 3, or 4.

### Output

Your program is to write to standard output. The output consists of *N*
lines, each containing a pair of code numbers each preceded by a sign
character. These are codes pairs that will direct the teleporter to the given
region sequence. Note that there must be no blank following a sign, but there
must be a single space after the first code number.

If there are several solutions your program can output any one of them. If there are no solutions your program should output the single integer 0.

### Sample Input 1

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

### Sample Output 1

+7 -1 -5 +2 -4 +3 +8 +6

### Sample Input 2

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

### Sample Output 2

+3 -2 -4 +5 -6 +1 +8 +7

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 32M

**Added:** Jul 25, 2010

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...