Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2015 - командный тур


1. Сломать последовательность

Автор задачи: Хаустов Павел
Источник: Региональная олимпиада по программированию 2015, командный тур
Ограничение по времени: 1 с.
Ограничение по памяти: 128 МБ

Имеется некоторая последовательность s, состоящая из n пар целых чисел (ai, bi), где i = 1, 2, ..., n. Паша очень любит последовательности, но терпеть не может порядок. Ему хочется узнать, можно ли переупорядочить последовательность s так, чтобы она НЕбыла:

  1. упорядочена в порядке неубывания значений ai
  2. упорядочена в порядке невозрастания значений ai;
  3. упорядочена в порядке неубывания значений bi;
  4. упорядочена в порядке невозрастания значений bi.

Ваша задача — написать программу, которая переупорядочит заданную последовательность требуемым образом или сообщит, что это сделать невозможно.

Входные данные

Первая строка входных данных содержит единственное целое число n — количество пар в последовательности s (1 ≤ n ≤ 105).

Далее следует n строк, i-я из которых описывает i-ю по порядку пару последовательности s двумя целыми числами ai и bi ( - 109ai, bi ≤ 109).

Выходные данные

Если переупорядочить последовательность s требуемым образом нельзя, то единственная строка выходных данных должна содержать строку «Impossibru». В противном случае, требуется вывести n строк, каждая из которых должна описывать очередной элемент переупорядоченной последовательности. Элементы должны быть упорядочены требуемым в задаче образом.

Примеры
Стандартный вводСтандартный вывод
5
1 6
1 5
2 3
3 2
5 2
2 3
5 2
1 6
1 5
3 2
1
2 28
Impossibru