Кубик-змійка#5305
Кубик-змійка — це механічна головоломка, яка складається з n^3 кубиків 1 \times 1 \times 1 і які з'єднані еластичною ниткою. Кожна пара сусідніх кубиків по нитці дотикається однією гранню і може вільно обертатися навколо осі, перпендикулярної цій грані. Кожні три послідовних кубики утворюють або пряму лінію, або кут у градусів. Не можна зігнути прямий відрізок змійки в кут або розпрямити кут у прямий — можна лише обрати, за допомогою обертання, в який із чотирьох напрямків змійка повертає на кожному куті. Мета — скласти з цієї змійки великий куб розміром n \times n \times n. Приклад змійки наведений на рисунку.
Не з кожної змійки можна скласти куб. Для цього необхідно, щоб усі прямі ділянки змійки складалися не більш ніж з кубиків.
Задаємо змійку послідовністю довжин її прямих ділянок, точніше, послідовністю відстаней між центрами першого і останнього кубика в кожній прямій ділянці. Наприклад, змійка на рисунку задається зліва направо так: 2~1~1~2~1~2~1~1~2~2~1~1~1~2~2~2~2.
У цій задачі пропонується розв'язати узагальнену версію цієї головоломки. Дана змійка з l \times w \times h клітинок. Укладіть її у прямокутний паралелепіпед розміром l \times w \times h клітинок або встановіть, що це неможливо.
У першому рядку дано чотири цілих числа , , , (1 \leq l, w, h \leq 4;~0 \leq m < lwh) — довжина, ширина і висота паралелепіпеда, а також кількість сегментів змійки. У другому рядку додатних цілих чисел — послідовність довжин прямих ділянок змійки. Гарантується, що змійка містить рівно l \times w \times h кубиків.
Якщо не можна укласти змійку в паралелепіпед, виведіть "Bit" у першому рядку. Інакше виведіть "Baba" у першому рядку, а в наступних l \times w \times h рядках — координати кубиків змійки по порядку, по три числа у рядку. Змійку слід виводити з того ж кінця, із якого вона починається у вхідному файлі. Числа x_i, y_i, z_i у (i+1)-му рядку мають задовольняти нерівності 0 \leq x_i < l, 0 \leq y_i < w, 0 \leq z_i < h. Усі кубики паралелепіпеда мають з'явитися у вихідному файлі рівно один раз, сусідні рядки повинні містити сусідні кубики, а повороти повинні повністю відповідати поворотам змійки. Змійка може починатися й закінчуватися в будь-якому кубику паралелепіпеда. Якщо існує кілька рішень, виведіть будь-яке з них.
Приклад 1