Нечесна гра

Європейський футбольний турнір має n команд-учасниць. У першому раунді проводиться n/2 матчів, де кожна команда грає проти іншої. Після кожного раунду лише переможці проходять далі. У другому раунді проводиться n/4 матчів, де кожен переможець першого раунду грає проти іншого переможця. Зрештою, залишаються дві команди, які змагаються у фіналі. Переможець фіналу стає чемпіоном турніру.

Голландська футбольна команда, можливо, не є найкращою у світі, але вона досить сильна. Вони можуть легко перемогти принаймні половину інших команд. Крім того, для кожної команди t, яку голландці не можуть перемогти, існує інша команда t', яка перемагає t, але програє голландській команді.

Тренер голландської команди хоче організувати турнір так, щоб їхня команда стала чемпіоном. Він знає, яка команда виграє у кожній парі команд, якщо вони зіграють між собою.

Задача

Ви знаєте, яка з двох команд виграє, якщо вони зіграють одна проти одної. (Оскільки це турнір на вибування, нічиї неможливі.) Ви також знаєте, що ваша улюблена команда може перемогти принаймні половину інших команд, і для кожної команди t, яку ваша улюблена команда не може перемогти, існує команда t', яка перемагає t, але програє вашій улюбленій команді.

Визначте розклад турніру так, щоб ваша улюблена команда виграла турнір.

Вхідні дані

Для кожного тестового випадку вхідні дані такі:

• Один рядок, що містить кількість команд n, де n є ступенем двійки і 2 ≤ n ≤ 1024. Команди пронумеровані від 1 до n, де команда 1 є вашою улюбленою командою.

• n рядків, кожен з яких містить рядок з n бінарних цифр. k-та цифра в j-му рядку є '1', якщо команда j точно виграє у команди k, інакше це '0'. Команда не може грати проти себе, тому j-та цифра в j-му рядку є '0'. Якщо j ≠ k, то k-та цифра в j-му рядку відрізняється від j-тої цифри в k-му рядку.

Вихідні дані

Для кожного тестового випадку виведіть n-1 рядків виходу, що визначають розклад турніру, який забезпечує перемогу команди 1.

Перші n/2 рядків описують перший раунд турніру. Наступні n/4 рядків описують другий раунд, якщо такий є, і так далі. Останній рядок описує фінальний матч.

Кожен рядок містить два цілі числа x і y, що вказують, що команда x грає матч проти команди y.

Якщо існує кілька розкладів турніру, де команда 1 виграє, будь-який з цих розкладів буде прийнятий як правильна відповідь.