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抰 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.