Nam được mẹ giao nhiệm vụ rèn luyện phép tính cộng cho em trai. Nam dự định vừa rèn luyện tính cộng vừa tạo niềm yêu thích tin học bằng cách cho em trai giải bài toán sau:

Cho một bảng số nguyên gồm có 𝑚 hàng và 𝑛 cột. Các hàng của bảng được đánh số từ 1 tới 𝑚 từ trên xuống dưới, các cột của bảng số được đánh số từ 1 tới 𝑛 từ trái qua phải. Giá trị của số nằm ở hàng 𝑖, cột 𝑗 (1 ≤ 𝑖 ≤ 𝑚; 1 ≤ 𝑗 ≤ 𝑛) được ký hiệu là 𝑎(𝑖,𝑗). Cần thực hiện lần lượt 𝑄 thao tác, thao tác thứ 𝑡 (1 ≤ 𝑡 ≤ 𝑄) được mô tả bằng bộ năm số 𝑥_𝑡 , 𝑦_𝑡 , 𝑢_𝑡 , 𝑣_𝑡 , 𝑐_𝑡 , thao tác này sẽ tăng tất cả các phần tử 𝑎(𝑖,𝑗) với mọi 𝑥_𝑡 ≤ 𝑖 ≤ 𝑢_𝑡 , 𝑦_𝑡 ≤ 𝑗 ≤ 𝑣_𝑡 lên một lượng là 𝑐_𝑡 (𝑐_𝑡 > 0).

Nam sẽ yêu cầu em trai ghi ra giấy tất cả các phần tử của bảng số sau khi đã thực hiện cả 𝑄 thao tác. Để kiểm tra xem em mình làm có đúng không, Nam phải tự mình tính toán ra được kết quả đúng trước đã. Sau một hồi tính toán, Nam đã có được bảng số sau khi thực hiện 𝑄 thao tác. Tuy nhiên, giá trị của các phần tử của bảng số kết quả khá lớn! Nam sợ rằng em trai mình sẽ gặp khó khăn khi thực hiện phép cộng giữa hai số lớn, do đó Nam quyết định bỏ đi một thao tác sao cho sau khi thực hiện 𝑄 − 1 thao tác còn lại, giá trị lớn nhất của bảng số là nhỏ nhất có thể.

Yêu cầu: Cho bảng số và dãy 𝑄 thao tác, gọi 𝑊𝑡 là giá trị lớn nhất trong bảng sau bỏ đi thao tác thứ 𝑡 (1 ≤ 𝑡 ≤ 𝑄), tính Min{𝑊₁,𝑊₂, … , 𝑊_𝑄}.

Dữ liệu:

- Dòng đầu chứa số hai số nguyên dương 𝑚, 𝑛;
- Tiếp theo là 𝑚 dòng, dòng thứ 𝑖 (1 ≤ 𝑖 ≤ 𝑚) gồm 𝑛 số nguyên không âm 𝑎(𝑖, 1), 𝑎(𝑖, 2), …, 𝑎(𝑖, 𝑛), các số có giá trị không vượt quá 10⁹.
- Dòng tiếp theo chứa số nguyên 𝑄 (𝑄 > 1);
- Tiếp theo là 𝑞 dòng, dòng thứ 𝑡 (1 ≤ 𝑡 ≤ 𝑄) gồm 5 số nguyên 𝑥_𝑡 , 𝑦_𝑡 , 𝑢_𝑡 , 𝑣_𝑡 , 𝑐_𝑡 (1 ≤ 𝑥_𝑡 ≤ 𝑢_𝑡 ≤ 𝑚, 1 ≤ 𝑦_𝑡 ≤ 𝑣_𝑡 ≤ 𝑛, 1 ≤ 𝑐_𝑡 ≤ 1000).

Kết quả:

Ghi ra một dòng duy nhất là giá trị nhỏ nhất của giá trị lớn nhất của bảng số sau khi loại bỏ đi đúng một thao tác.