Một đàn gấu túi bị biến đổi gien tràn vào thành phố Brisbane. Bạn phải đưa mọi người đi lánh nạn đến nơi an toàn.

Đường phố Brisbane được bố trí trên một lưới ô vuông lớn. Có \(R\) đường ngang chạy từ đông sang tây, được đánh số từ \(0\) đến \(R-1\) theo thứ tự từ bắc xuống nam, và \(C\) đường dọc chạy từ bắc xuống nam, được đánh số từ \(0\) đến \(C-1\) theo thứ tự từ tây sang đông.

Gấu túi xâm chiếm từ phía bắc, còn mọi người chạy trốn về phía nam. Trên đường ngang, mọi người có thể đi theo cả hai hướng. Trên đường dọc, họ chỉ được đi về phía nam.

Nút giao giữa đường ngang \(P\) và đường dọc \(Q\) được ký hiệu là \((P,Q)\). Mỗi đoạn đường nối hai nút giao kề nhau có một số gấu túi; số lượng này có thể thay đổi theo thời gian. Bạn cần hướng dẫn từng người đi từ một nút giao cho trước trên đường ngang \(0\) đến một nút giao cho trước trên đường ngang \(R-1\), sao cho tổng số gấu túi trên các đoạn đường họ đi qua nhỏ nhất có thể.

Ban đầu, bạn được cho kích thước lưới và số gấu túi trên mỗi đoạn đường. Sau đó có một chuỗi \(E\) sự kiện theo thứ tự. Một sự kiện thay đổi cập nhật số gấu túi trên một đoạn đường. Một sự kiện chạy trốn cho biết một người đến một nút giao trên đường ngang \(0\) và yêu cầu tìm số gấu túi nhỏ nhất người đó phải đi qua để đến một nút giao cho trước trên đường ngang \(R-1\).

Cài đặt

Nộp một tệp cài đặt các hàm C/C++ sau và dùng #include "wombats.h":

void init(int R, int C, int H[5000][200], int V[5000][200]);
void changeH(int P, int Q, int W);
void changeV(int P, int Q, int W);
int escape(int V1, int V2);

Dữ liệu vào

init(R, C, H, V) cung cấp bản đồ ban đầu và cho phép khởi tạo các biến toàn cục, cấu trúc dữ liệu. Hàm này được gọi đúng một lần, trước mọi lời gọi changeH, changeV hoặc escape. R là số đường ngang và C là số đường dọc. Phần dữ liệu được sử dụng của H có kích thước \(R \times (C-1)\): H[P][Q] là số gấu túi trên đoạn ngang từ \((P,Q)\) đến \((P,Q+1)\). Phần dữ liệu được sử dụng của V có kích thước \((R-1) \times C\): V[P][Q] là số gấu túi trên đoạn dọc từ \((P,Q)\) đến \((P+1,Q)\).

changeH(P, Q, W) được gọi khi số gấu túi trên đoạn ngang từ \((P,Q)\) đến \((P,Q+1)\) thay đổi thành W. Các tham số thỏa mãn \(0 \le P \le R-1\), \(0 \le Q \le C-2\), \(0 \le W \le 1\,000\).

changeV(P, Q, W) được gọi khi số gấu túi trên đoạn dọc từ \((P,Q)\) đến \((P+1,Q)\) thay đổi thành W. Các tham số thỏa mãn \(0 \le P \le R-2\), \(0 \le Q \le C-1\), \(0 \le W \le 1\,000\).

escape(V1, V2) mô tả một người chạy từ \((0,V1)\) đến \((R-1,V2)\), với \(0 \le V1,V2 \le C-1\).

Dữ liệu ra

Mỗi lời gọi escape phải trả về tổng số gấu túi nhỏ nhất có thể gặp trên một đường đi hợp lệ giữa hai nút giao được yêu cầu, xét các thay đổi đã xảy ra. Các hàm init, changeH, changeV không trả về giá trị.

Ràng buộc

• Giới hạn thời gian: 20 giây.
• Giới hạn bộ nhớ: 256 MiB.
• \(2 \le R \le 5\,000\).
• \(1 \le C \le 200\).
• Có tổng cộng không quá \(500\) lời gọi changeH và changeV.
• Có không quá \(200\,000\) lời gọi escape.
• Số gấu túi trên mỗi đoạn đường tại mọi thời điểm nằm trong khoảng từ \(0\) đến \(1\,000\).

Phân nhóm

Mỗi nhóm tuân theo các ràng buộc chung và các điều kiện bổ sung sau.

Trình chấm mẫu

Trình chấm mẫu đọc tệp wombats.in:

• Dòng 1: R C.
• Dòng \(2\) đến \(R+1\): mỗi dòng chứa một hàng của H, lần lượt từ H[0][0] ... H[0][C-2] đến H[R-1][0] ... H[R-1][C-2].
• Dòng \(R+2\) đến \(2R\): mỗi dòng chứa một hàng của V, lần lượt từ V[0][0] ... V[0][C-1] đến V[R-2][0] ... V[R-2][C-1].
• Dòng tiếp theo: E.
• \(E\) dòng tiếp theo: mỗi dòng mô tả một sự kiện, theo đúng thứ tự xảy ra.

Nếu \(C=1\), không cần các dòng trống dành cho H (các dòng \(2\) đến \(R+1\) trong định dạng trên).

Các sự kiện có định dạng 1 P Q W cho changeH(P, Q, W), 2 P Q W cho changeV(P, Q, W), và 3 V1 V2 cho escape(V1, V2).

Ví dụ

3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1

2
7
5