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

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

Электронный плакат представляет собой прямоугольную таблицу символов. Изначально он состоит из $$$h$$$ строк и $$$w$$$ столбцов. Затем контроллер последовательно выполняет $$$q$$$ команд.

Команда задаётся двумя целыми числами $$$a$$$, $$$b$$$ и строчной латинской буквой $$$c$$$. Пусть непосредственно перед командой плакат имел $$$h$$$ строк и $$$w$$$ столбцов. После команды его размеры становятся равны

$$$$$$ \max(h,a) \times \max(w,b). $$$$$$

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

Если оба указанных размера не превосходят текущие размеры плаката, команда ничего не изменяет.

Выведите плакат после выполнения всех команд.

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

В первой строке даны три целых числа $$$h$$$, $$$w$$$ и $$$q$$$ ($$$1 \le h, w \le 1000$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — начальное количество строк, начальное количество столбцов и количество команд.

В следующих $$$h$$$ строках записано по $$$w$$$ строчных латинских букв — начальное содержимое плаката.

В следующих $$$q$$$ строках даны два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le 2 \cdot 10^5$$$) и строчная латинская буква $$$c_i$$$ — описание очередной команды.

Команды выполняются в том порядке, в котором они записаны во входных данных.

Гарантируется, что в любой момент $$$h \cdot w \le 10^6$$$, в том числе после всех операций, когда плакат самый большой.

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

Выведите итоговое содержимое плаката: по одной строке для каждой строки таблицы.

Примеры
Входные данные
1 1 3
a
1 3 x
3 2 y
2 5 z
Выходные данные
axxzz
yyyzz
yyyzz
Входные данные
2 2 4
ab
cd
1 1 x
3 4 p
2 3 z
4 4 q
Выходные данные
abpp
cdpp
pppp
qqqq