Кубик-змійка
Кубик-змійка - це механічна ломиголовка, яка складається з n^3 кубиків 1×1×1, через які проходить еластичний шнур. Сусідні кубики на шнурі дотикаються однією гранню і можуть вільно обертатись один відносно іншого по осі, перпендикулярній цій грані. Кожні три кубика, які йдуть підряд, утворюють або пряму лінію, або кут 90 градусів. Зігнути прямий відрізок змійки в кут чи виспрямити кут у прямий відрізок не можна; можна лише при допомозі поворотів вибрати, у яку з чотирьох сторін змійка повертається у кожному куті. Мета - зібрати з цієї змійки великий куб n×n×n. Приклад змійки показано на рисунку.
Звичайно, не з довільної змійки можна зібрати куб - для цього необхідно, як мінімум, щоб усі прямі ділянки змійки складались не більше ніж з n кубиків.
Будемо задавати змійку послідовністю довжин її прямих шматків, точніше, послідовністю відстаней між центрами першого та останнього кубиків у кожному прямому шматку. Наприклад, змійка, зображена на рисунку, задається зліва праворуч наступним чином: 2 1 1 2 1 2 1 1 2 2 1 1 1 2 2 2 2.
У цій задачі пропонується розв'язати узагальнену версію цієї ломиголовки. Задано змійку із l×w×h клітинок. Укладіть її у прямокутний паралелепіпед розміром l×w×h клітинок або виясніть, що це неможливо.
Вхідні дані
У першому рядку вхідного файлу записано через пропуск чотири цілих числа - l, w, h та m (1 ≤ l, w, h ≤ 4; 0 ≤ m < lwh); туть l, w та h - це довжина, ширина та висота паралелепіпеда, відповідно, а m - кількість ланок у змійці. У другому рядку записано m цілих чисел через пропуск - послідовність додатних довжин прямих шматків змійки. Гарантується, що задана змійка містить рівно l×w×h кубиків.
Вихідні дані
Якщо задану змійку у паралелепіпед укласти неможливо, виведіть "Bit" у першому рядку вихідного файлу. У протилежному випадку у першому рядку вхідного файлу виведіть "Baba", а у наступних l×w×h рядках - координати кубиків змійки, по три числа у рядку. Змійку слід виводити з того ж кінця, з якого вона починається у вхідному файлі. Числа x_i, y_i та z_i у (i+1)-му рядку повинні задовольняти нерівностям 0 ≤ x_i < l, 0 ≤ y_i < _w та 0 ≤ z_{i }< h. Крім того, усі кубики паралелепіпеда l×w×h повинні зустрітись у вихідному файлі по одному разу, у сусідніх рядках повинні бути сусідні кубики, а повороти повинні у точності відповідати поворотам змійки. Змійка може починатись та закінчуватись у довільному кубику паралелепіпеда. Якщо розв'язків декілька, дозволяється виводити довільний з них.