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

Лучше поздно, чем никогда

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

G. Припечатывальщик

Ограничение времени: 1.0 секунды
Ограничение памяти: 256 МБ
Согласно новому законопроекту, на каждый документ вместо одной печати должно ставиться целых q одинаковых печатей. Это усложняет подделку документов, а также уменьшает уровень безработицы, ведь теперь каждой компании приходится содержать целый штат припечатывальщиков!
Никита устроился стажёром-припечатывальщиком и сегодня получил своё первое задание. Перед ним лежит документ размером n × m. Никита мысленно разделил его на n · m одинаковых квадратиков. Ещё у Никиты есть печать, матрица которой имеет размер a × b и разделена на a · b одинаковых квадратиков. Каждый квадратик матрицы либо чёрный, либо бесцветный, то есть не оставляет следов на бумаге.
Будем описывать квадратик в документе или в матрице печати парой чисел (x, y) — номером строки и номером столбца, при этом строки нумеруются сверху вниз начиная с единицы, а столбцы нумеруются слева направо начиная с единицы. Никита может совершить операцию припечатывания (x, y), то есть совместить верхний левый квадратик матрицы печати с квадратиком (x, y) документа и нажать на печать. При этом все чёрные квадратики матрицы покрасят лежащие под ними квадратики документа. В ходе операции припечатывания матрица должна целиком находиться в границах документа.
Никита сделал q операций припечатывания (xi, yi). Задание было бы выполнено, но не всё так просто. Назовём перекрашенным квадратик, который был покрашен более одного раза. В компании действует правило, согласно которому документ, содержащий хотя бы k перекрашенных квадратиков, признаётся неразборчивым. Обратите внимание, что квадратик, который был покрашен три или более раз, всё равно считается за один перекрашенный квадратик. Определите номер припечатывания, после которого документ стал неразборчивым, или выведите финальный вид документа.

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

В первой строке даны целые числа n, m и k (1 ≤ n, m ≤ 1000; 1 ≤ k ≤ 100), разделённые пробелом, — высота, ширина документа и минимальное недопустимое количество перекрашенных квадратиков соответственно.
Во второй строке даны целые числа a и b (1 ≤ an; 1 ≤ bm), разделённые пробелом, — высота и ширина матрицы печати соответственно.
В следующих a строках описана матрица печати. Каждая из этих строк состоит из b символов «.» или «#». Символ «.» обозначает бесцветный квадратик, а символ «#» — чёрный квадратик.
В следующей строке дано целое число q (1 ≤ q ≤ 105) — количество операций припечатывания.
В следующих q строках описаны операции. Каждая из них задаётся целыми числами x и y (1 ≤ xna + 1; 1 ≤ ymb + 1), разделёнными пробелом, — номером строки и столбца соответственно.

Результат

Если существует операция припечатывания, после выполнения которой документ становится неразборчивым, выведите в единственной строке “Wasted after stamp #s”, где s — номер операции. Операции припечатывания пронумерованы с единицы в порядке описания.
Иначе выведите описание документа после выполнения всех операций. Описание состоит из n строк по m символов в каждой, формат описания документа совпадает с форматом описания матрицы печати.

Примеры

исходные данныерезультат
4 3 2
3 2
#.
.#
..
2
1 1
2 2
#..
.#.
..#
...
4 3 1
3 2
#.
.#
..
2
1 1
2 2
Wasted after stamp #2
Автор задачи: Кирилл Бороздин
Источник задачи: Контест "Лучше поздно, чем никогда"
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2134. Припечатывальщик