Задача D. Индикатор загрузки

Автор:И. Бураго   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Во многих менеджерах загрузки — программах для скачивания файлов из Интернет — для наглядного отображения процесса загрузки используются различные индикаторы, одна из разновидностей которых имеет следующий вид.

Индикатор загрузки представляет собой поле n × m пикселей, отражающее состояние загрузки некоторого файла размером n ⋅ m байт. Все пиксели индикатора нумеруются от 1 до n ⋅ m слева направо сверху вниз, при этом пиксель c номером i окрашен в чёрный цвет, если i-й по счёту байт файла уже загружен, и в белый цвет — в противном случае.

Для ускорения загрузки файл был разделён на равные фрагменты по b байт, каждый из которых загружается одновременно. Байты внутри одного фрагмента загружаются последовательно от начала к концу.

Поскольку индикатор в целом зачастую очень большой, в окно программы может помещаться только его прямоугольная часть. Требуется по изображению этой части определить, каково минимально и максимально возможное число загруженных байт файла в предположении, что в каждый фрагмент загружено одинаковое число байт.

Формат входного файла

В первой строке входного файла находятся целые числа n m b. Вторая строка содержит четыре числа r1 c1 r2 c2 — координаты видимой части индикатора. Следующие r2 − r1 + 1 строк по c2 − c1 + 1 символов каждая описывают видимую часть изображения: строки с r1-й по r2-ю, столбцы с c1-го по c2-й. Символ '=' (ASCII 61) обозначает чёрный пиксель, символ '.' (ASCII 46) — белый.

Формат выходного файла

Выходной файл должен содержать два целых числа — минимально и максимально возможное число байт, загруженных к данному моменту.

Ограничения

1 ≤ n, m ≤ 104, 1 ≤ b ≤ n ⋅ m, n ⋅ m делится на b нацело.

1 ≤ r1 ≤ r2 ≤ n, 1 ≤ c1 ≤ c2 ≤ m, r2 − r1 ≤ 100, c2 − c1 ≤ 100.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 7 5
2 3 2 3
.
0 28
2
5 7 5
1 5 3 7
.==
==.
..=
21 21

0.041s 0.007s 15