题目描述

有一个尺寸为 $n \times m$ 的长方形画布，每个像素点的颜色用 $0$ 到 $255$ 之间的整数表示。现在有一个特殊的油漆桶工具，当你点击画布上的某个像素点 $(x, y)$ 时，所有与该点颜色值相差不超过 $d$ 的连通像素都会被染成该点的颜色。

具体来说，若你点击像素点 $(x, y)$，其颜色值为 $c$，则所有满足以下条件的像素点 $(i, j)$ 都会被染成颜色 $c$：

1. 从 $(x, y)$ 出发，可以通过上下左右四个方向移动到达与原始点的颜色差的绝对值不超过d的位置 $(i, j)$；
2. 将能够到达的位置变为之前的颜色 $c$

给定画布初始状态和若干次点击操作，输出最终的画布状态。

输入格式

• 第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 100$），表示画布的行数和列数。
• 接下来 $n$ 行，每行包含 $m$ 个整数 $c_{i,j}$（$0 \leq c_{i,j} \leq 255$），表示画布的初始颜色。
• 下一行包含一个整数 $q$（$1 \leq q \leq 1000$），表示操作次数。
• 接下来 $q$ 行，每行包含三个整数 $x$, $y$, $d$（$1 \leq x \leq n$, $1 \leq y \leq m$, $0 \leq d \leq 255$），表示点击坐标为 $(x, y)$ 的像素点（坐标从 $1$ 开始），且颜色差值阈值为 $d$。

输出格式

输出 $n$ 行，每行 $m$ 个整数，表示经过所有操作后画布的最终颜色。

样例

样例输入

4 4  
3 3 0 4  
3 2 2 8  
1 2 11 12  
13 14 15 16  
2  
2 2 2  
3 3 1  

样例输出

2 2 2 2  
2 2 2 8  
2 2 11 11  
13 14 15 16  

样例解析

数据范围与提示

• 数据规模：$1 \leq n, m \leq 100$，$1 \leq q \leq 1000$，$0 \leq c_{i,j}, d \leq 255$。