Входные данные: стандартный ввод Выходные данные: стандартный вывод Ограничения на память: 32 MB Время на тест: 2 секунды Тесты к задаче:Скачать
ЗАДАЧА
Однажды прекрасная страна Утопия была разорена войной. Когда враждебность утихла, страна была разделена на четыре области по долготе (линия север-юг) и широте (линия восток-запад). Точку пересечения этих линий обозначили (0,0). Все четыре части претендовали на название Утопия, но со временем их стали называть Утопия 1 (северо-восточная), 2 (северо-западная), 3 (юго-западная) и 4 (юго-восточная). Каждая точка в любом регионе определялась расстоянием на восток и расстоянием на север от (0,0). Эти расстояния могли быть отрицательными, то есть точка в Утопии 2 обозначалась парой (отрицательное, положительное), в Утопии 3 - парой (отрицательное, отрицательное),
в Утопии 4 - парой (положительное, отрицательное), в Утопии 1 - парой положительных чисел.
Наибольшей проблемой являлось то, что гражданам запрещалось пересекать границы. К счастью, изобретательный участник IOI из Утопии разработал простой способ телепортации. Телепортер требует кодовые числа, каждое из которых может быть использовано только один раз. Вам необходимо провести телепортер с его начальной позиции (0,0) через области Утопии в требуемом порядке. У вас будет последовательность из N номеров областей, в каждой из которых вы должны приземлиться, при этом не имеет значения, где именно в области вы приземлились. Вас могут попросить приземлиться в одной и той же области несколько раз подряд. После того, как вы покинете точку (0,0), вам нельзя попадать на границы областей.
Исходные 2N кодовых числа вы должны записать как последовательность N кодовых пар, добавляя знак плюс или минус перед каждым числом. Если вы находитесь в точке (x,y) и используете кодовую пару (+u, v), вы будете телепортированы в точку (x+u, y v). У вас есть 2N чисел, и вы можете использовать их в любом выбраном вами порядке, каждое со знаком плюс или минус.
Допустим, у вас есть кодовые числа 7, 5, 6, 1, 3, 2, 4, 8, и вы должны провести телепортер по последовательности областей с номерами 4, 1, 2, 1. Последовательность кодовых пар (+7, 1), ( 5,+2), ( 4,+3), (+8,+6) позволяет это сделать, телепортируя вас из точки (0,0) последовательно в точки (7, 1), (2,1), ( 2,4) и (6,10). Эти точки расположены в Утопии 4, Утопии 1, Утопии 2 и
Утопии 1 соответственно.
ЗАДАНИЕ
Вам дано 2N различных кодовых чисел и последовательность N номеров областей, указывающих, где должен приземлиться телепортер. Постройте последовательность кодовых пар из заданных кодовых чисел, которая проведет телепортер через заданную последовательность областей.
ВВОД
Ваша программа должна читать стандартный ввод. Первая строка содержит положительное целое N (1≤N≤10000). Вторая строка содержит 2N различных целых кодовых чисел (1≤кодовое число≤100000), разделенных одиночными пробелами. Последняя строка содержит последовательность N номеров областей, каждый из которых есть 1, 2, 3 или 4.
ВЫВОД
Ваша программа должна писать в стандартный вывод. Вывод должен состоять из N строк. Каждая строка должна содержать пару кодовых чисел, перед каждым из которых указан знак (плюс или минус). Эти кодовые пары будут направлять телепортер по заданной последовательности областей. Заметьте, что не должно быть пробелов между знаком и числом, но должен быть один пробел после первого кодового числа.
Если существует несколько решений, ваша программа должна вывести любое из них. Если решений нет, ваша программа должна вывести единственное целое 0.