Chúng ta sẽ biểu diễn khu vực vẽ của MS Paint dưới dạng một lưới hình chữ nhật gồm các ô đơn vị được chia thành ~R~ hàng và ~S~ cột. Mỗi ô của lưới đại diện cho một pixel có thể được tô màu bằng một trong ~105~ màu khác nhau. Khi người dùng áp dụng công cụ đổ màu với màu ~A~ vào một pixel ~(r, s)~ đã được tô màu ~B~, thì tất cả các pixel trong khu vực lân cận đơn sắc của pixel ~(r, s)~ sẽ thay đổi màu của chúng thành màu ~A~. Khu vực lân cận đơn sắc của một pixel ~(r, s)~ là một tập hợp các pixel có thể đạt được bằng cách đi từ ~(r, s)~ theo bốn hướng chung (lên, xuống, trái và phải) mà không thay đổi màu sắc của pixel theo cách đó. Lưu ý rằng pixel ~(r, s)~ chính nó cũng là một phần của khu vực lân cận đơn sắc của nó.

Bạn được cung cấp một hình ảnh ban đầu được vẽ trong MS Paint cùng với ~Q~ hướng dẫn cần thực hiện theo thứ tự cho trước. Mỗi hướng dẫn cho bạn biết bạn nên áp dụng công cụ đổ màu vào pixel nào và với màu gì. Nhiệm vụ của bạn là hiển thị hình ảnh trông như thế nào sau khi tất cả các hướng dẫn được thực hiện.

Input

• Dòng đầu tiên chứa các số nguyên ~R~ và ~S~ từ mô tả bài toán.
• Mỗi trong số ~R~ dòng tiếp theo chứa S số nguyên không âm nhỏ hơn ~100 000~ đại diện cho hình ảnh ban đầu được vẽ trong MS Paint. Cụ thể, số thứ ~j~ trong hàng ~i~ của hình ảnh đại diện cho màu của pixel ~(i, j)~.
• Dòng tiếp theo chứa một số nguyên ~Q~ từ mô tả bài toán.
• Dòng thứ ~i~ trong ~Q~ dòng tiếp theo chứa các số nguyên ~r_i, s_i~ và ~c_i~ ~(1 \leq r_i \leq R, 1 \leq s_i \leq S, 0 \leq c_i < 100 000)~, đại diện cho hướng dẫn thứ ~i~ cho bạn biết sử dụng công cụ đổ màu với màu ~c_i~ vào pixel ~(ri, si)~.

Output

Bạn nên đưa ra trạng thái cuối cùng của hình ảnh theo định dạng giống như đã được cung cấp trong đầu vào.

Chú ý

• 8 điểm thỏa mãn ~1 \leq R \times S \leq 10 000, 1 \leq Q \leq 10 000~.
• 9 điểm thỏa mãn ~R = 1, 1 \leq S \leq 200 000, 1 \leq Q \leq 100 000~.
• 31 điểm thỏa mãn ~1 \leq R \times S \leq 200 000, 1 \leq Q \\leq 100 000~. Mỗi pixel sẽ luôn được tô màu hoặc là màu ~0~ hoặc là màu ~1~.
• 52 điểm thỏa mãn ~1 \leq R \times S \leq 200 000, 1 \leq Q \leq 100 000~.

Sample Input 1

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

Sample Ouput 1

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

Sample Input 2

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

Sample Ouput 2

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

Sample Input 3

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

Sample Ouput 3

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

Giải thích

Giải thích của ví dụ đầu tiên Hình từ mô tả bài toán tương ứng với đầu vào của ví dụ đầu tiên. Màu trắng tương ứng với số 0, màu đỏ tương ứng với số 1, màu xanh tương ứng với số 2, màu xanh lá cây tương ứng với số 3 và màu vàng tương ứng với số 4.