Задача 5L. Игровой движок ≡

Условие

Всем известно, что игра DOOM 1993 года написана на языке программирования C. Программист Александр очень любит ставить эту игру на самые необычные и непредназначенные для этого устройства, такие как экран микроволновой печи или домашний электронный градусник.

Однако Александр тот ещё олд и считает, что язык C недостаточно старый, поэтому он решил переписать игру на язык Паскаль.

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

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

Формат входных данных

В первой строке входных данных задано два числа H и W - высота и ширина экрана в пикселях. (1 ≤ H, W ≤ 2000).

Во второй строке располагается число N - количество врагов на сцене. (0 ≤ N ≤ 500).

В следующих N строках располагается по 5 чисел. Первые четыре числа x₁, y₁, x₂, y₂ - концы одной из диагоналей прямоугольника в пикселях. После чего идет число d - расстояние до врага. (1 ≤ x₁, x₂ ≤ W,   1 ≤ y₁, y₂ ≤ H,   1 ≤ d ≤ 10⁹).

Каждая из сторон прямоугольников параллельна какой-то стороне экрана.

Враги могут накладываться друг на друга, то есть быть в одной точке на одном расстоянии.

Формат выходных данных

Выведите матрицу A размера H × W, в которой элемент A_{i, j} равен расстоянию до ближайшего врага в пикселе с координатами (i, j). Если в этом пикселе нет врагов, то выведите 0.

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

5 5
2
2 2 5 3 1
3 1 4 4 2

0 0 0 0 0 
0 0 2 2 0 
0 1 1 1 1 
0 1 1 1 1 
0 0 2 2 0 

3 3
2
1 3 2 2 1
2 1 3 2 1

1 1 0 
1 1 1 
0 1 1