Нечестная игра

В европейском футбольном турнире участвуют 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 побеждает, любое из этих расписаний будет принято как правильный ответ.