1296 - 边界着色

通过次数

16

提交次数

59

Time Limit : 1 秒
Memory Limit : 128 MB

给你一个大小为 m x n 的整数矩阵 grid ,表示一个网格。另给你三个整数 rowcolcolor 。网格中的每个值表示该位置处的网格块的颜色。

两个网格块属于同一 连通分量 需满足下述全部条件:

  • 两个网格块颜色相同

  • 在上、下、左、右任意一个方向上相邻

连通分量的边界 是指连通分量中满足下述条件之一的所有网格块:

  • 在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻

  • 在网格的边界上(第一行/列或最后一行/列)

请你使用指定颜色 color 为所有包含网格块 grid[row][col]连通分量的边界 进行着色,并返回最终的网格 grid

Input

第一行为2个整数,m,n,分别表示网格块的行和列

以下m行,每行n列,表示网格块的颜色

第 m+2 行包含3个整数,row,col和color,分别表示连通分量的起始行和列,以及着色的颜色

Output

着色后的网格块

Examples

Input

2 2
1 1
1 2
0 0 3

Output

3 3
3 2

Input

2 3
1 2 2
2 3 2
0 1 3

Output

1 3 3
2 3 3

Hint

  • m == grid.length

  • n == grid[i].length

  • 1 <= m, n <= 50

  • 1 <= grid[i][j], color <= 1000

  • 0 <= row < m

  • 0 <= col < n