ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC, Восточный подрегион, Екатеринбург, октябрь 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Японский кроссворд

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Решение японских кроссвордов (они часто называются "Закраска числами") — очень популярное развлечение среди новых русских. В этом виде кроссвордовов клетки должны закрашиваться чёрным или оставаться пустыми в соответствии с числами, заданными на сторонах прямоугольной сетки. Если всё сделано правильно, чёрные клетки складываются в картинку. Числа на сторонах сетки — длины последовательных отрезков закрашенных клеток в строке или столбце. Например, ключ "4 8 3" означает, что есть отрезки из четырёх, восьми и трёх заполненных клеток, в таком порядке, с хотя бы одной пустой клеткой между последовательными группами. Конечно, программисты не настолько умны, как новые русские, поэтому мы не просим вас решить весь кроссворд. Вашей задачей будет написать программу, которая находит как можно больше информации о каждой клетке одной строки кроссворда по некоторой уже имеющейся информации об этой строке.

Исходные данные

Первая строка содержит длину строки L (1 ≤ L ≤ 400) и число групп последовательных клеток, которые должны быть закрашены K (0 ≤ K ≤ L). Вторая строка содержит K целых чисел — длины этих групп. Третья строка содержит L символов, описывающих текущую информацию о клетках этой строки (эта информация может быть получена анализом данных столбцов и других строк):
'.' означает клетку, которая определённо пуста,
'X' (латинская заглавная) означает клетку, которая определённо должна быть закрашена,
'?' означает, что об этой клетке нет информации.

Результат

Выведите строку, содержащую L символов, описывающих наиболее полную информацию о клетках строки в том же формате, что и во вводе, или слово "Impossible", если исходная информация противоречива, и никакая строка не может соответствовать входным данным.

Примеры

исходные данныерезультат
10 2
4 2
?????.?X??
?XXX?.?X?.
9 0

??????.X?
Impossible
Автор задачи: Станислав Васильев
Источник задачи: Quarter-Final of XXXI ACM ICPC - Yekaterinburg - 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1508. Японский кроссворд