Задача C. Класс ≡

Условие

Доктор Странный действительно странный. На каждой лекции он вычисляет заполненность класса и если она маленькая, уменьшает все оценки в семестре на 1. Поэтому студенты хотят максимизировать заполненность класса.

Заполненность класса — это минимум из заполненности рядов и заполненности колонок. Заполненность колонок — это максимальное количество студентов в одной колонке, а заполненность рядов  — максимальное количество студентов в ряду.

Например, есть 16 студентов, изображенных на картинке слева (занятые парты темные). Заполненность рядов этого расположения составляет 5 ( в четвертом ряду), а заполненность колонок 3 (1, 3, 5, 6 колонки). Итак, заполненность класса равна 3. Но если студенты пересядут как показано на картинке справа, то заполненность колонок станет равна 4 (5-ая колонка), и тогда заполненность класса также станет равна 4.

Студентам Доктора Странного необходимо знать расположение, которое максимизирует заполненность класса, поэтому они просят вас написать программу которая ее вычислит.

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

В первой строке входного файла содержатся три числа: n, r и c — количество студентов, рядов и колонок в классе.

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

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

Следующие r строк должны содержать оптимальное расположение студентов. Каждая строка должна содержать описание одного ряда. Описание ряда — это строка из c символов, либо ".", либо "#", где "." означает пустую парту, а "#" — заполненную. Если допустимо несколько оптимальных расположений, выведите любое.

Ограничения

1 ≤ r, c ≤ 100, 1 ≤ n ≤ r × c.

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

16 4 6

4
.####.
#..###
#...##
###.##