Inspired by Kazimir Malevich’s masterpiece “Black Square”, Peter Palevich is planning to create his own
version. He prepared a rectangular grid containing m x n white cells arranged in m rows of n cells each.
Peter painted some of the cells black, so that the black cells formed a square of size s x s cells. But later
that day Peter became disappointed with his painting and destroyed it, cutting it to horizontal stripes
of size 1 x n and burning them in the fireplace.
Next morning Peter changed his mind and decided to restore his painting. He tried to find its remains
in the fireplace, and fortunately one of the stripes, namely the k-th from the top, survived the fire.
Now Peter wonders whether it is possible to restore the painting based on this stripe. Help him to do it.
There are many test cases. They end with EOF.
The first line of each test case contains four integer numbers: m, n, s and k (1 ≤ m, n ≤ 5000;
1 ≤ s ≤ min(m, n); 1 ≤ k ≤ m).
The second line contains n characters and describes the k-th line of the painting, ‘.’ stands for a white
cell, ‘*’ stands for a black cell.
If the initial painting can be uniquely restored, output “Unique”.
If there are several paintings that could have been painted by Peter, output “Ambiguous”.
If there are no possible paintings, output “Impossible”.
4 4 1 2 ..*. 4 4 2 2 ..** 4 4 3 2 .*.*
Unique Ambiguous Impossible
Migrated from old NTUJ.
ACM ICPC 2011–2012, NEERC, Northern Subregional Contest
| No. | Testdata Range | Score |
|---|