IOI '02 - Yong-In, Korea

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 $2N$ 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 $2N$ 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 $2N$ 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 Specification

Your program is to read from standard input. The first line contains a positive integer $N$ $(1\le N\le 10000)$. The second line contains the $2N$ distinct integer code numbers $(1\le \text{code number}\le 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 Specification

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