Trong thế giới LQDOJ cấp cao nơi thuật toán quyết định mọi thứ, PhuocThien đã nâng cấp hệ thống từ dãy một chiều lên ma trận năng lượng kích thước \(n \times m\), nhưng chính điều này đã mở ra điểm yếu chí mạng khiến hệ thống dễ bị tấn công hơn bao giờ hết. Ngay khi phát hiện ra điều đó, hai đối thủ nguy hiểm conghieupt2555 và hbl lập tức khai thác triệt để và bắt đầu tung ra các đòn “phủ vùng” cực kỳ phức tạp lên toàn bộ ma trận. Không còn những thao tác đơn giản theo đoạn, mỗi đòn tấn công giờ đây ảnh hưởng theo cả hai chiều, tạo thành những vùng biến đổi lan rộng khó kiểm soát.
Mỗi đòn tấn công có dạng \((x_1, y_1, x_2, y_2, k)\) và với mọi ô \((i, j)\) thỏa mãn \(x_1 \le i \le x_2\) và \(y_1 \le j \le y_2\) thì giá trị bị thay đổi theo công thức \(a_{i,j} = a_{i,j} + (i - x_1 + 1)\cdot (j - y_1 + 1)\cdot k\). Điều này đồng nghĩa mỗi đòn tạo ra một “ma trận tăng trưởng” mà giá trị không chỉ tăng theo hàng mà còn tăng theo cột, khiến tốc độ biến đổi trở nên cực kỳ nhanh. Các đòn tấn công chồng chéo lên nhau tạo thành những vùng nhiễu loạn phức tạp khiến việc mô phỏng trực tiếp gần như không khả thi trong giới hạn thời gian.
PhuocThien buộc phải tìm ra cách tính toán chính xác trạng thái cuối cùng của toàn bộ ma trận sau khi tất cả các đòn tấn công kết thúc, nếu không toàn bộ hệ thống sẽ sụp đổ do sai lệch dữ liệu tích lũy.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, q\).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên \(a_{i,j}\) (\(1 \le n, m \le 1000\), \(|a_{i,j}| \le 10^9\)).
• \(q\) dòng tiếp theo, mỗi dòng gồm năm số \(x_1, y_1, x_2, y_2, k\) (\(1 \le x_1 \le x_2 \le n\), \(1 \le y_1 \le y_2 \le m\), \(|k| \le 10^4\), \(q \le 10^5\)).

Output

• In ra ma trận sau khi tất cả các đòn tấn công kết thúc, mỗi dòng gồm \(m\) số.

Example

2 2 1
1 1
1 1
1 1 2 2 1

2 3
3 5

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

0 2 4
0 4 8

Scoring

• Subtask \(1\) (\(50\%\) điểm): \(1 \le n, m \le 300\), \(q \le 5000.\)
• Subtask \(2\) (\(50\%\) điểm): \(1 \le n, m \le 1000\), \(q \le 10^5.\)