ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1867. Нанотехнологии

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Специалисты из лаборатории нанотехнологий Уральского федерального университета занимаются созданием вычислителя, работающего на уровне отдельных атомов. Недавно они узнали, что если правильно расположить на плоскости n атомов тантала, то можно построить на их основе квантовый компьютер, обладающий недостижимыми ранее характеристиками.
К сожалению, теория описывает только некоторые физические характеристики системы атомов, но не их конфигурацию в целом. Физики должны вычислить, как именно нужно расположить атомы, чтобы добиться желаемого эффекта. Сканирующий туннельный микроскоп, который физики используют для своих опытов, может поместить атом тантала только в точки, координаты которых выражены целым числом нанометров, по модулю не превышающим 106.
Чтобы определить координаты атомов, учёные обратились за помощью к вам. Они избавились от лишней физической информации и предоставили вам только квадраты расстояний между всеми парами атомов.

Исходные данные

Первая строка содержит единственное целое число n — общее количество атомов (2 ≤ n ≤ 100). Далее в n строках записана матрица aij размера n × n. Число aij равно требуемому квадрату расстояния между атомами с номерами i и j (0 ≤ aij ≤ 109; aij = aji; aii = 0). Все aij целые.

Результат

Если существует ответ, удовлетворяющий данной матрице квадратов расстояний, выведите n строк. i-я строка должна содержать два целых числа, по модулю не превосходящих 106 — координаты i-го атома. Если существует несколько возможных ответов, выведите любой из них. Если разместить атомы требуемым образом невозможно, выведите «Impossible».

Примеры

исходные данныерезультат
3
0 1 4
1 0 1
4 1 0
0 0
1 0
2 0
3
0 1 5
1 0 1
5 1 0
Impossible
3
0 1 0
1 0 1
0 1 0
5 -5
5 -4
5 -5
Автор задачи: Сергей Пупырев (подготовка — Иван Бурмистров)
Источник задачи: Открытый командный чемпионат УрФУ по программированию — 2011