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