e-olymp
Məsələlər

Черный квадрат

Черный квадрат

Вдохновленный шедевром Казимира Малевича "Черный квадрат", Петр Палевич решил создать собственную версию картины. Он приготовил полотно в виде прямоугольной сетки с 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".

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 4 1 2
..*.
Çıxış verilənləri #1
Unique
Giriş verilənləri #2
4 4 2 2
..**
Çıxış verilənləri #2
Ambiguous
Giriş verilənləri #3
4 4 3 2
.*.*
Çıxış verilənləri #3
Impossible
Mənbə 2011 ACM NEERC, Northern Subregional Contest, Санкт-Петербург, Октябрь 29, Задача B