eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Кубик-змійка

Кубик-змійка

Кубик-змійка - це механічна ломиголовка, яка складається з \textbf{n^3} кубиків \textbf{1}×\textbf{1}×\textbf{1}, через які проходить еластичний шнур. Сусідні кубики на шнурі дотикаються однією гранню і можуть вільно обертатись один відносно іншого по осі, перпендикулярній цій грані. Кожні три кубика, які йдуть підряд, утворюють або пряму лінію, або кут \textbf{90} градусів. Зігнути прямий відрізок змійки в кут чи виспрямити кут у прямий відрізок не можна; можна лише при допомозі поворотів вибрати, у яку з чотирьох сторін змійка повертається у кожному куті. Мета - зібрати з цієї змійки великий куб \textbf{n}×\textbf{n}×\textbf{n}. Приклад змійки показано на рисунку. \includegraphics{https://static.e-olymp.com/content/fa/fa5c225e2e380f3eaa74c66cf84d79a5f48bb238.jpg} Звичайно, не з довільної змійки можна зібрати куб - для цього необхідно, як мінімум, щоб усі прямі ділянки змійки складались не більше ніж з \textbf{n} кубиків. Будемо задавати змійку послідовністю довжин її прямих шматків, точніше, послідовністю відстаней між центрами першого та останнього кубиків у кожному прямому шматку. Наприклад, змійка, зображена на рисунку, задається зліва праворуч наступним чином: \textbf{2 1 1 2 1 2 1 1 2 2 1 1 1 2 2 2 2}. У цій задачі пропонується розв'язати узагальнену версію цієї ломиголовки. Задано змійку із \textbf{l}×\textbf{w}×\textbf{h} клітинок. Укладіть її у прямокутний паралелепіпед розміром \textbf{l}×\textbf{w}×\textbf{h} клітинок або виясніть, що це неможливо. \InputFile У першому рядку вхідного файлу записано через пропуск чотири цілих числа - \textbf{l}, \textbf{w}, \textbf{h} та \textbf{m} (\textbf{1} ≤ \textbf{l}, \textbf{w}, \textbf{h} ≤ \textbf{4}; \textbf{0 }≤ \textbf{m }< \textbf{lwh}); туть \textbf{l}, \textbf{w} та \textbf{h} - це довжина, ширина та висота паралелепіпеда, відповідно, а \textbf{m} - кількість ланок у змійці. У другому рядку записано \textbf{m} цілих чисел через пропуск - послідовність додатних довжин прямих шматків змійки. Гарантується, що задана змійка містить рівно \textbf{l}×\textbf{w}×\textbf{h} кубиків. \OutputFile Якщо задану змійку у паралелепіпед укласти неможливо, виведіть "\textbf{Bit}" у першому рядку вихідного файлу. У протилежному випадку у першому рядку вхідного файлу виведіть "\textbf{Baba}", а у наступних \textbf{l}×\textbf{w}×\textbf{h} рядках - координати кубиків змійки, по три числа у рядку. Змійку слід виводити з того ж кінця, з якого вона починається у вхідному файлі. Числа \textbf{x_i}, \textbf{y_i} та \textbf{z_i} у \textbf{(i+1)}-му рядку повинні задовольняти нерівностям \textbf{0} ≤ \textbf{x_i} < \textbf{l}, \textbf{0} ≤ \textbf{y_i} < _w та \textbf{0 }≤ \textbf{z_\{i \}}< \textbf{h}. Крім того, усі кубики паралелепіпеда \textbf{l}×\textbf{w}×\textbf{h} повинні зустрітись у вихідному файлі по одному разу, у сусідніх рядках повинні бути сусідні кубики, а повороти повинні у точності відповідати поворотам змійки. Змійка може починатись та закінчуватись у довільному кубику паралелепіпеда. Якщо розв'язків декілька, дозволяється виводити довільний з них.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3 3 3 17
2 1 1 2 1 2 1 1 2 2 1 1 1 2 2 2 2
Вихідні дані #1
Baba
0 0 0
1 0 0
2 0 0
2 1 0
1 1 0
1 1 1
1 1 2
1 2 2
1 2 1
1 2 0
2 2 0
2 2 1
2 1 1
2 0 1
1 0 1
0 0 1
0 1 1
0 1 0
0 2 0
0 2 1
0 2 2
0 1 2
0 0 2
1 0 2
2 0 2
2 1 2
2 2 2
Автор Ivan Kazmenko