Ta biểu diễn bảng vẽ của MS Paint bằng một bảng hình chữ nhất gồm các ô vuông đơn vị được chia thành $R$ hàng và $S$ cột. Mỗi ô vuông của bảng biễu diễn một pixel có thể được tô bằng một trong ${10}^5$ màu khác nhau. Khi người dùng sử dụng dụng cụ bucket tool* với màu $A$ lên pixel $(r,s)$ mà đang có màu $B$, thì tất cả pixel trong vùng đơn sắc của pixel $(r,s)$ chuyển sang màu $A$. Vùng đơn sắc của pixel $(r,s)$ được định nghĩa là một tập hợp các pixel có thể đi tới xuất phát từ $(r,s)$ theo một trong bốn hướng (lên, xuống, trái, phải) mà không thay đổi màu trên đường đi. Lưu ý rằng pixel $(r,s)$ cũng là một phần trong vùng đơn sắc của chính nó.

Bạn nhận được hình vẽ ban đầu trên MS Paint cũng với $Q$ chỉ dẫn cần được thực hiện theo thứ tự được cho. Mỗi chỉ dẫn cho bạn biết vị trí pixel cần sử dụng bucket tool lên và màu cần dùng. Nhiệm vụ của bạn là in ra bảng vẽ cuối cùng sau khi thực hiện các chỉ dẫn.

*Bucket tool: Dụng cụ đổ màu trong MS Paint.

Input

Dòng đầu tiên chứa các số nguyên $R$ và $S$.

$R$ dòng tiếp theo, mỗi dòng chứa $S$ số nguyên không âm bé hơn $100000$ thể hiện hình vẽ ban đầu trong MS Paint.

Dòng tiếp theo chứa số nguyên $Q$.

$Q$ dòng tiếp theo, dòng thứ $i$ chứa các số nguyên $r_i{s}_i$ và $c_i(1\le r_i\le R,1\le s_i\le S,0\le Q<100000)$, thể hiện chỉ dẫn thứ $i$ yêu cần bạn sử dụng bucket tool có màu $c_i$ lên pixel $(r_i,s_i)$.

Output

In ra trạng thái cuối cùng của hình vẽ với định dạng như đã cho trong input.

Sample 1

Input

12 11
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1
1 1 1 0 0 0 0 0 1 1 1
1 1 0 0 0 0 0 0 0 1 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 0 0 0 0 0 0 1
1 1 0 0 0 2 0 0 0 1 1
0 1 1 0 0 2 0 0 1 1 0
0 0 1 1 0 0 0 1 1 0 0
0 0 0 1 1 1 1 1 0 0 0
2
5 5 3
6 2 4

Output

1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 4 4 4 1 1 1 1
1 1 1 4 4 4 4 4 1 1 1
1 1 4 4 4 4 4 4 4 1 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 4 4 4 4 4 4 1
1 1 4 4 4 2 4 4 4 1 1
0 1 1 4 4 2 4 4 1 1 0
0 0 1 1 4 4 4 1 1 0 0
0 0 0 1 1 1 1 1 0 0 0

Giải thích

Hình vẽ trong đề bài tương ứng với input của test mẫu $1$. Màu trắng tương ứng với số $0$, màu đỏ tương ứng với số $1$, màu xanh dương tương ứng với số $2$, màu xanh lá tương ứng với số $3$ và màu vàng tương ứng với số $4$.

Sample 2

Input

4 4
1 0 1 3
1 3 2 2
3 3 1 2
2 2 1 3
3
1 2 3
3 2 1
4 2 3

Output

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

Sample 3

Input

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

Output

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

Ràng buộc

• $7$ test đầu thỏa mãn $1\le R\times S\le 10000$, $1\le Q\le 10000$.
• $3$ test tiếp theo thỏa mãn $R=1$, $1\le S\le 200000$, $1\le Q\le 100000$.
• $5$ test tiếp theo thỏa mãn $1\le R\times S\le 200000$, $1\le Q\le 100000$. Mỗi pixel trong mọi thời điểm sẽ chỉ được tô màu $0$ hoặc $1$.
• $9$ test còn lại thỏa mãn $1\le R\times S\le 200000$, $1\le Q\le 100000$.