G. Потоп
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

В одну из точек поля начинает течь вода в течение k секунд, за секунду втекает 1 единица воды. Если единица воды попадает в яму, она уменьшает глубину ямы на 1, при этом яма становится плоскостью, если её глубина до попадания была равна 1. Если вода попадает на плоскость, то она может двигаться в любую клетку поля, до которой можно добраться, двигаясь по смежным между собой клеткам. Две клетки называются смежными, если у них есть общая сторона. Все клетки в пути должны быть плоскостями, за исключением последней. При этом вода течет в самую глубокую яму, до которой она может добраться. Если таких ям несколько, вода течет в яму в клетке с координатами (i, j), у которой номер numi, j наибольший. Если все ямы заполнены, вода вытекает за пределы поля и ничего не меняется. За один момент времени может глубина может уменьшиться максимум у одной ямы.

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

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

В первой строке находятся 5 чисел - n, m, x, y, k. 1 ≤ n, m ≤ 100, 1 ≤ x ≤ n, 1 ≤ y ≤ m, 1 ≤ k ≤ 1012. n и m — это размеры поля, x и y — соответственно номер строки и столбца, куда течет вода, k — длительность эксперимента.

В следующих n строках записано по m чисел ai, j — глубина ямы, находящейся в клетке (i, j). Если в клетке находится плоскость, aij = 0. 0 ≤ aij ≤ 1012, 1 ≤ i ≤ n, 1 ≤ j ≤ m.

В следующих n строках записано по m чисел numi, j — номера клеткок. 1 ≤ numij ≤ n·m, 1 ≤ i ≤ n, 1 ≤ j ≤ m. Все номера клеток различны.

Числа в каждой строке между собой разделены пробелами

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

Надо вывести n строк по m чисел, разделенных пробелами — состояния клеток поля в таком же формате, как во входных данных.

Примеры
Входные данные
2 2 1 1 10
0 10
10 10
1 3
2 4
Выходные данные
0 5 
5 10
Входные данные
4 4 1 1 11
1 2 3 4
1 1 1 1
1 1 1 1
1 1 1 1
16 15 14 5
9 8 13 12
4 7 6 11
1 2 3 10
Выходные данные
0 0 0 1 
1 1 0 0 
1 1 1 1 
1 1 1 1