Олимпиадный тренинг

Задача . B. Проверка печати

Задача

Крис работает в крупной компании «Blake Technologies». Ему как лучшему инженеру было поручено разработать уникальный принтер, который будет рисовать горизонтальные и вертикальные полоски. Первый прототип принтера уже готов, и Крис собирается протестировать его, а вас просит написать программу, проверяющую, что результат печати совпадает с ожидаемым.

Принтер умеет печатать только на прямоугольных клетчатых листах размера n × m. Представим лист как таблицу, состоящую из n строк и m столбцов. Строки нумеруются сверху вниз целыми числами от 1 до n, а столбцы — слева направо целыми числами от 1 до m. Изначально все клетки таблицы покрашены в цвет 0.

Ваша программа должна уметь выполнять два типа операций:

Покрасить все клетки строки r_i в цвет a_i;
Покрасить все клетки столбца c_i в цвет a_i.

Если при выполнении операции i какая-то клетка уже была покрашена, то она всё равно меняет свой цвет на цвет a_i.

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

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

В первой строке входных данных записаны три целых числа n, m и k (1 ≤ n, m ≤ 5000, n·m ≤ 100 000, 1 ≤ k ≤ 100 000) — размеры листа и количество операций соответственно.

В следующих k строках идут запросы двух видов:

1 r_i a_i (1 ≤ r_i ≤ n, 1 ≤ a_i ≤ 10⁹), означает, что строка r_i красится в цвет a_i;
2 c_i a_i (1 ≤ c_i ≤ m, 1 ≤ a_i ≤ 10⁹), означает, что столбец c_i красится в цвет a_i.

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

Выведите n строк по m чисел в каждой строке — итоговые цвета клеток таблицы.

Примечание

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

$\text{[math]}$

Примеры

№	Входные данные	Выходные данные
1	3 3 3 1 1 3 2 2 1 1 2 2	3 1 3 2 2 2 0 1 0
2	5 3 5 1 1 1 1 3 1 1 5 1 2 1 1 2 3 1	1 1 1 1 0 1 1 1 1 1 0 1 1 1 1

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет