G2. Молчат дома (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.

Вы любите дома и решили попробовать изобразить их в виде прямоугольных таблиц, состоящих из символов '+' и '#'. Знак '+' символизирует стену дома, а знак '#' — его окно. Чтобы дом выглядел реалистично, никакие символы-окна не должны находиться на краю таблицы или соприкасаться с другими символами-окнами по углу или стороне. Например, следующие дома не являются реалистичными:

++++++++++++
+#+++#++#+#+
++++#+++#+#+
+#++++++++++

А эти дома являются реалистичными:

++++++++++++
+#++++++#+#+
++++++++++++
+#+++++++#++
++++++++++++

Напишите программу, которая по заданным числам $$$n, m, k$$$ выводит любую возможную таблицу из $$$n$$$ строк и $$$m$$$ столбцов, изображающую реалистичный дом с $$$k$$$ окнами, либо определяет, что таких таблиц не существует.

Входные данные

В единственной строке вводятся три целых числа $$$n, m, k$$$ ($$$1 \le n,m \le 10^5$$$, $$$1 \le n \cdot m \le 10^5$$$, $$$0 \le k \le 10^9$$$).

Выходные данные

Выведите таблицу из $$$n$$$ строк и $$$m$$$ столбцов, изображающую реалистичный дом с $$$k$$$ окнами, если такая существует. Все символы в каждой строке таблицы должны выводиться слитно. Если существует несколько подходящих таблиц, вы можете вывести любую из них.

Если таких таблиц нет, выведите строку «impossible» строчными латинскими буквами и без кавычек.

Примеры
Входные данные
5 5 3
Выходные данные
+++++
++#++
+++++
+#+#+
+++++
Входные данные
3 4 0
Выходные данные
++++
++++
++++
Входные данные
3 3 1000
Выходные данные
impossible