Специалисты из лаборатории нанотехнологий Уральского федерального университета занимаются созданием вычислителя, работающего на уровне отдельных атомов. Недавно они узнали, что если правильно расположить на плоскости n атомов тантала, то можно построить на их основе квантовый компьютер, обладающий недостижимыми ранее характеристиками.

К сожалению, теория описывает только некоторые физические характеристики системы атомов, но не их конфигурацию в целом. Физики должны вычислить, как именно нужно расположить атомы, чтобы добиться желаемого эффекта. Сканирующий туннельный микроскоп, который физики используют для своих опытов, может поместить атом тантала только в точки, координаты которых выражены целым числом нанометров, по модулю не превышающим 10⁶.

Чтобы определить координаты атомов, учёные обратились за помощью к вам. Они избавились от лишней физической информации и предоставили вам только квадраты расстояний между всеми парами атомов.

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

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