Маршрутизація#1258

Маршрутизація

1 секунда

128 мегабайтів

Легка

Ви працюєте інженером в Inane Collaboration for Performance Computing, де відповідаєте за проєктування мережі взаємозв'язку для комп'ютерів. Мережа організована у вигляді прямокутної таблиці з $2 n - 1$ 2n-1 рядків, у кожному з яких $2^{n - 1}$ 2^{n-1} перемикачів. Перемикач — це пристрій із двома вхідними дротами ( $X$ та $Y$ ) і двома вихідними дротами ( $X^{'}$ X' та $Y^{'}$ Y'). Якщо перемикач вимкнений, дані з входу $X$ передаються на вихід $X^{'}$ X', а з $Y$ — на $Y^{'}$ Y'. Якщо він увімкнений, то $X$ під'єднується до $Y^{'}$ Y', а $Y$ — до $X^{'}$ X'. Крім того, у верхньому та нижньому рядках розміщено $2^{n}$ 2^n комп'ютерів, і між парами цих комп'ютерів потрібна передача повідомлень. Дані з двох різних джерел не можуть проходити одним дротом, але обидва можуть проходити через один перемикач, якщо використовують різні входи.

Ви вирішили, що найбільш придатною є мережа з топологією Бенеса. $1$ -Benes-мережа — це просто один перемикач. Для $n > 1$ n>1 $n$ -Benes-мережа може бути збудована рекурсивно таким чином:

У першому (верхньому) рядку є $2^{n - 1}$ 2^{n-1} перемикачів; $j$ -й перемикач ( $0 \leq j < 2^{n - 1}$ 0 \leq j < 2^{n-1}) отримує вхідні дані від комп'ютерів $2 j$ та $2 j + 1$ 2j+1 (комп'ютери у верхньому та нижньому рядках позначаються числами від $0$ до $2^{n} - 1$ 2^n-1 зліва направо).
Між першим і другим рядками перемикачів до вихідних дротів застосовується досконала перестановка-shuffle. Вихід $j$ під'єднується з входом $j^{'}$ j' у наступному рядку, де $j^{'}$ j' — результат правої циклічної зміни $n$ -бітного двійкового запису $j$ на один розряд (входи та виходи нумеруються зліва направо).
Якщо $n > 2$ n > 2, наступні ряди перемикачів (до передостаннього включно) формують дві підмережі $(n - 1)$ (n-1)-Benes — одну ліворуч, іншу праворуч.
До виходів застосовується зворотна перестановка (inverse shuffle), після чого додається останній ряд перемикачів.

Наприклад, на малюнку вище показано Benes-мережу для $n = 3$ n=3 (квадрати — це перемикачі; комп'ютери у верхньому та нижньому рядах не намальовані, але позначені числами від $0$ до $7$ ). На малюнку показано можливий стан перемикачів. Квадрат, де перетинаються дві лінії, означає, що перемикач увімкнено. Такий стан дозволяє одночасно прокладати шляхи зв'язку між комп'ютерами $0$ , $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ в нижньому ряду і $3$ , $7$ , $4$ , $0$ , $2$ , $6$ , $1$ , $5$ у верхньому відповідно.

Вам дано пари комп'ютерів $(a, b)$ , які повинні бути з'єднані одночасно (де $a$ — комп'ютер у нижньому ряду, а $b$ — у верхньому). Це потрібно зробити по незалежних дротах (wire-disjoint paths). Необхідно визначити стан усіх перемикачів, щоб це виконати.

Вхідні дані

Перший рядок кожного тесту — ціле число $n$ ( $1 \leq n \leq 13$ 1 \leq n \leq 13), тобто кількість пар комп'ютерів для з'єднання, як описано вище. Рядок з $n = 0$ n=0 позначає кінець введення і не обробляється.

Кожен рядок з $n > 0$ n>0 доповнюється ще одним, який містить $2^{n}$ 2^n цілих чисел. $i$ -те число ( $0 \leq i < 2^{n}$ 0 \leq i < 2^n) — це комп'ютер у верхньому ряду, з яким $i$ -й комп'ютер нижнього ряду має зв'язатись.

Вихідні дані

Для кожного тесту виведіть $2 n - 1$ 2n-1 рядків, кожен з яких є бітовим рядком довжини $2^{n - 1}$ 2^{n-1}, що показує для кожного перемикача, чи має він бути увімкнений ( $1$ ), чи вимкнений ( $0$ ).

Вхідні дані гарантують існування принаймні одного розв'язку. Якщо розв'язків декілька — виведіть лексикографічно найменший. Тобто, рядок верхнього ряду має бути мінімальним; при рівності — другий рядок мінімальний і так далі.

Виводи для різних тестових випадків розділяйте порожнім рядком.

Приклади

Приклад 1