Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
第一届北京大学游戏对抗邀请赛将与 ACM-ICPC 北京赛区同时举行,丰厚奖金等你来拿!
Utopia Divided
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 835Accepted: 363Special Judge


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.


Your program is to read from standard input. The first line contains a positive integer N (1 <= N <= 10000). The second line contains the 2N 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.


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

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

Sample Output

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


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator