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

Чорний квадрат

Чорний квадрат

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Натхненний шедевром Казимира Малевича "Чорний квадрат", Петро Палевіч вирішив створити власну версію картини. Він приготував полотно у вигляді прямокутної сітки з m × n білими квадратами - m рядків по n комірок кожна.

Петро пофарбував деякі клітини в чорний колір так, що чорні клітинки сформували квадрат розміром s × s клітин. Але на наступний день Петро розчарувався у своєму творінні і знищив його, розрізавши полотно горизонтальними смугами розміру 1 × n, після чого спалив їх у каміні.

Наступного ранку Петро передумав і вирішив відновити картину. Він спробував знайти її останки в каміні, і, на щастя, одну зі смуг, а саме, k-у зверху, вогонь не зачепив.

Тепер Петро задумався, чи можна відновити картину на основі цієї смуги. Допоможіть йому зробити це.

Вхідні дані

Перший рядок містить чотири цілі числа: m, n, s та k (1m, n5000, 1s ≤ min (m, n), 1km).

Другий рядок містить n символів і описує k-ий рядок картини, '.' означає білу клітинку, '\*' означає чорну клітинку.

Вихідні дані

Якщо зображення може бути однозначно відновлено, то слід вивести "Unique". Якщо існує декілька варіантів відновлення картини, то вивести "Ambiguous". Якщо жодної відповідної картини не існує, вивести "Impossible".

Приклад

Вхідні дані #1
4 4 1 2
..*.
Вихідні дані #1
Unique
Вхідні дані #2
4 4 2 2
..**
Вихідні дані #2
Ambiguous
Вхідні дані #3
4 4 3 2
.*.*
Вихідні дані #3
Impossible
Джерело 2011 ACM NEERC, Northern Subregional Contest, Санкт-Петербург, Октябрь 29, Задача B