Гіперкуб
Розгляньмо 4-гіперкуб, відомий як тесеракт. Одиничний цільний тесеракт — це 4D фігура, яка є опуклою оболонкою 16 точок з декартовими координатами (±1/2, ±1/2, ±1/2, ±1/2), що є його вершинами. Він має 32 ребра (1D), 24 квадратні грані (2D) і 8 кубічних 3-граней (3D), відомих як комірки. Ми будемо вивчати порожнисті тесеракти і визначимо тесеракт як межу цільного тесеракта. Тобто тесеракт є об'єднанням 8 цільних кубів (його комірок), які перетинаються між собою по 24 квадратним граням, 32 ребрам і 16 вершинам.
Розріжемо тесеракт уздовж 17 з його 24 граней так, щоб він залишався зв'язаним по 7 граням, які залишилися непошкодженими. Розгорнемо тесеракт на 3D гіперплощині шляхом обертання його утворюючих кубів уздовж граней, які залишилися неторканими, поки всі його комірки не опиняться в одній і тій же 3D-гіперплощині. Результат називається 3-мережею тесеракта. Цей процес є природним узагальненням розрізання і розгортання 3D куба на 2D площині для отримання 2-мережі куба, що складається з 6 квадратів.
У цій задачі вам дано деревоподібний 8-полікуб у 3D просторі, відомий як октокуб. Октокуб — це колекція 8 одиничних кубічних комірок, з'єднаних одна з одною гранями. Більш формально, перетин кожної пари кубічних комірок, що складають октокуб, або порожній, або точка, або одиничний відрізок (1D), або одиничний квадрат (2D). Даний октокуб є деревоподібним у наступному сенсі. Розгляньмо граф суміжності октокуба — граф з 8 вершинами, що відповідають його 8 коміркам. Між парами сусідніх комірок у графі суміжності існує ребро. Дві комірки октокуба є суміжними, якщо їх перетином є квадрат. Комірки, що перетинаються по точці або по відрізку, не вважаються суміжними. Октокуб називається деревоподібним, якщо його граф суміжності є деревом.
Ваше завдання полягає в тому, щоб визначити, чи є даний деревоподібний октокуб 3-мережею тесеракта. Тобто чи може цей октокуб, поміщений на гіперплощину в просторі 4D, бути складений у просторі 4D уздовж квадратів перетину його комірок з тесерактом.
Наприклад, подивіться нижче на ліву картинку. Вона показує дротяну рамку деревоподібного октокуба. Обертайте комірку GHLKG[1]H[1]L[1]K[1] навколо площини GHLK і комірку FGKJF[2]G[2]K[2]J[2] навколо площини FGKJ на кут 90 градусів у 4-му вимірі поза оригінальною гіперплощиною. У результаті точка G[1] з'єднається з G[2], а точка K[1] з'єднається з K[2]. Грань GKK[2]G[2] склеїться з гранню GKK[1]G[1]. Результат показано справа. 4-те вимір ортогонально спроєктовано на 3 і показано в перспективі. Точки, які вийшли з вихідної гіперплощини, позначені порожніми точками.
Обертайте EFJIE[1]F[1]J[1]I[1] навколо EFJI і EHLIE[2]H[2]L[2]I[2] навколо EHLI. Результат показано на рисунку зліва. Інші кроки наступні. Обертайте MNOPQRST навколо MNOP, потім обертайте MNOPQRST і IJKLMNOP навколо IJKL і обертайте ABCDEFGH навколо EFGH. Останній крок — склеювання всіх граней разом для отримання тесеракта, який показано справа.
Вхідні дані
Перший рядок містить три цілі числа m, n, k — ширину, глибину і висоту коробки, що містить заданий октокуб (1 ≤ m, n, k ≤ 8). Наступні k груп рядків описують прямокутні шари коробки зверху вниз. Кожен шар описується n рядками по m символів. Рядок містить символи '.' — порожнє місце, або 'x' — одиниця куба. Вхідні дані гарантовано описують деревоподібний октокуб.
Вихідні дані
Виведіть слово "Yes", якщо заданий октокуб можна скласти в тесеракт, і "No" інакше.