Маршрутизація
Ви працюєте інженером в Інституті Високопродуктивних Обчислень, де відповідаєте за проектування мережі взаємодії для комп'ютерів. Мережа організована у вигляді прямокутної матриці з 2n - 1 рядків, кожен з яких має 2^(n−1) перемикачів. Перемикач — це пристрій з двома вхідними проводами, X та Y, і двома вихідними проводами, X' та Y'. Якщо перемикач вимкнений, дані з входу X передаються на вихід X', а дані з Y на Y'. Якщо він увімкнений, X з'єднується з Y', а Y з X'. Крім того, у верхньому та нижньому рядках є 2n комп'ютерів, і повідомлення потрібно передавати між їхніми парами. Зверніть увагу, що дані з двох різних джерел не можуть ділити один провід, але обидва шматки даних можуть проходити через один перемикач на різних входах.
Ви дійшли висновку, що мережа, яка найкраще підходить для ваших цілей, має топологію Бенеса. 1-мережа Бенеса — це просто перемикач. Для n > 1 n-мережа Бенеса може бути побудована рекурсивно наступним чином:
• У першому (верхньому) рядку є 2^(n−1) перемикачів так, що перемикач j (0 ≤ j < 2^(n−1)) має вхідні дані від комп'ютерів 2j та 2j + 1 (ми позначаємо комп'ютери у верхньому та нижньому рядках цілими числами від 0 до 2^n − 1 включно, зліва направо).
• Потім до вихідних проводів між першим і другим рядками перемикачів застосовується досконала перестановка, що означає, що вихід номер j у рядку з'єднаний з входом номер j' у наступному рядку, де j' отримується шляхом обертання n-бітного шаблону, що представляє j у двійковій системі, на один біт вправо (знову ж таки, входи та виходи нумеруються зліва направо).
• Якщо n > 2, наступні рядки перемикачів, до (і включно) передостаннього, утворюють дві (n - 1) - мережі Бенеса, одну з лівого боку та іншу з правого боку.
• Нарешті, до виходів застосовується зворотна перестановка, і додається останній рядок перемикачів.
Наприклад, на малюнку вище показана мережа Бенеса для n = 3 (квадрати представляють перемикачі; комп'ютери у верхньому та нижньому рядках не намальовані, але позначені цілими числами від 0 до 7). На малюнку показано можливий стан перемикачів, квадрати, де дві лінії перетинаються, є перемикачами, які були увімкнені. Ви можете перевірити, що цей стан дозволяє одночасно встановити шляхи зв'язку від комп'ютерів 0, 1, 2, 3, 4, 5, 6, 7 внизу до 3, 7, 4, 0, 2, 6, 1, 5 вгорі, відповідно.
Вам надано набір пар (a, b) комп'ютерів для одночасного з'єднання (де a — це комп'ютер у нижньому рядку, а b — комп'ютер у верхньому рядку) за допомогою шляхів, що не перетинаються, і ви повинні знайти, як вибрати стан усіх перемикачів, щоб це можна було здійснити.
Вхідні дані
Перша строка кожного тестового випадку — це ціле число n (1 ≤ n ≤ 13), що означає, що у вас є 2^n пар комп'ютерів для з'єднання, як описано вище. Строка з n = 0 позначає кінець введення і не повинна оброблятися.
Кожна строка з n > 0 буде слідувати за іншою строкою, що містить 2^n цілих чисел. i-те ціле число (0 ≤ i < 2^n) буде комп'ютером у верхньому рядку, з яким i-й комп'ютер у нижньому рядку повинен спілкуватися.
Вихідні дані
Вихід для кожного випадку повинен мати 2n - 1 рядків, кожен з яких містить бінарний рядок довжиною 2^(n−1), що вказує, для кожного перемикача, чи він повинен бути увімкнений (1) або вимкнений (0).
Вхідні дані завжди матимуть принаймні одне рішення. У разі кількох рішень, поверніть лексикографічно найменше. Тобто, рядок у верхньому рядку повинен бути лексикографічно найменшим; у разі рівності, рядок у другому рядку повинен бути лексикографічно найменшим і так далі.
Виходи для різних тестових випадків повинні бути розділені порожнім рядком.