Bazza và Shazza chơi trên một lưới gồm \(R\) hàng, đánh số từ \(0\) đến \(R-1\), và \(C\) cột, đánh số từ \(0\) đến \(C-1\). Ô ở hàng \(P\), cột \(Q\) được ký hiệu là \((P,Q)\). Mỗi ô chứa một số nguyên không âm; ban đầu tất cả đều bằng \(0\).

Ở mỗi bước, Bazza có thể thực hiện một trong hai thao tác:

• Cập nhật ô \((P,Q)\) bằng cách gán một số nguyên cho ô đó.
• Yêu cầu Shazza tính ước chung lớn nhất (ƯCLN) của tất cả các số nguyên trong hình chữ nhật có hai góc đối diện \((P,Q)\) và \((U,V)\), bao gồm cả các ô ở biên và hai ô góc.

Bazza thực hiện \(N_U+N_Q\) bước, gồm \(N_U\) lần cập nhật và \(N_Q\) lần yêu cầu tính toán, trước khi chán trò chơi và ra ngoài chơi cricket. Hãy tính đúng các câu trả lời cho Shazza.

Cài đặt

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

void init(int R, int C);
void update(int P, int Q, long long K);
long long calculate(int P, int Q, int U, int V);

Các tệp mẫu game.c và game.cpp có hàm gcd2(X, Y) tính ƯCLN của hai số nguyên không âm. Khi \(X=Y=0\), hàm này trả về \(0\). Hàm đủ nhanh để đạt toàn bộ số điểm; thời gian chạy trong trường hợp xấu nhất tỷ lệ với \(\log(X+Y)\).

Các số trong lưới có thể rất lớn, vì vậy người dùng C/C++ được khuyến cáo dùng kiểu long long.

Dữ liệu vào

init(R, C) cung cấp số hàng R và số cột C của lưới, cho phép khởi tạo biến toàn cục và cấu trúc dữ liệu. Hàm được gọi đúng một lần, trước mọi lời gọi update hoặc calculate.

update(P, Q, K) được gọi khi Bazza gán giá trị K cho ô \((P,Q)\). Các tham số thỏa mãn \(0 \le P \le R-1\), \(0 \le Q \le C-1\), \(0 \le K \le 10^{18}\). Giá trị mới có thể trùng với giá trị đang có.

calculate(P, Q, U, V) yêu cầu ƯCLN của tất cả các số trong hình chữ nhật có góc trên trái \((P,Q)\) và góc dưới phải \((U,V)\), bao gồm cả biên. Các tham số thỏa mãn \(0 \le P \le U \le R-1\) và \(0 \le Q \le V \le C-1\).

Dữ liệu ra

Mỗi lời gọi calculate phải trả về ƯCLN của tất cả các số trong hình chữ nhật được yêu cầu. Nếu tất cả các số đó bằng \(0\), hàm phải trả về \(0\). Các hàm init và update không trả về giá trị.

Ràng buộc

• \(1 \le R,C \le 10^9\).
• \(0 \le K \le 10^{18}\) với mọi giá trị được gán vào một ô.
• Giới hạn số thao tác, thời gian và bộ nhớ được cho trong bảng phân nhóm dưới đây.

Phân nhóm

Các cột \(N_U\) và \(N_Q\) lần lượt giới hạn tổng số lần cập nhật và tổng số lần yêu cầu tính toán. Mỗi nhóm tuân theo các ràng buộc chung và toàn bộ giới hạn trên cùng một hàng.

Trình chấm mẫu

Trình chấm mẫu đọc tệp game.in. Dòng đầu chứa R C N, trong đó \(N=N_U+N_Q\). Tiếp theo là \(N\) dòng, mỗi dòng mô tả một thao tác theo đúng thứ tự thực hiện:

• 1 P Q K tương ứng với update(P, Q, K).
• 2 P Q U V tương ứng với calculate(P, Q, U, V).

Ví dụ

2 3 9
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
2 0 0 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1

5
4
1
2