Mansur thích nuôi ngựa như tổ tiên của mình. Hiện nay anh có đàn ngựa lớn nhất Kazakhstan, nhưng trước đây không phải lúc nào cũng vậy. Cách đây \(N\) năm, Mansur chỉ là một dzhigit (tiếng Kazakhstan nghĩa là chàng trai trẻ) và có đúng một con ngựa. Anh mơ ước kiếm được nhiều tiền để trở thành một bai (người rất giàu có).

Đánh số các năm từ \(0\) đến \(N-1\) theo thứ tự thời gian, nên năm \(N-1\) là năm gần đây nhất. Thời tiết mỗi năm ảnh hưởng đến sự tăng trưởng của đàn ngựa. Với năm \(i\), Mansur nhớ hệ số tăng trưởng nguyên dương \(X[i]\): nếu bắt đầu năm với \(h\) con ngựa thì cuối năm, trước khi bán, sẽ có \(h \cdot X[i]\) con.

Ngựa chỉ được bán vào cuối năm. Với mỗi năm \(i\), Mansur nhớ số nguyên dương \(Y[i]\), là giá bán một con ngựa vào cuối năm đó. Sau mỗi năm, anh có thể bán số ngựa tùy ý trong đàn, mỗi con cùng giá \(Y[i]\).

Mansur muốn biết số tiền lớn nhất anh có thể có hiện nay nếu đã chọn thời điểm bán ngựa tốt nhất trong \(N\) năm. Bạn vinh dự là khách dự toi (ngày lễ) của Mansur và được anh nhờ trả lời câu hỏi này.

Trong buổi tối, trí nhớ của Mansur dần tốt hơn nên anh đưa ra \(M\) lần cập nhật. Mỗi lần thay đổi một giá trị \(X[i]\) hoặc \(Y[i]\), rồi anh lại hỏi số tiền lớn nhất có thể thu được. Các cập nhật có tính tích lũy: mỗi câu trả lời phải xét mọi cập nhật trước đó. Một giá trị \(X[i]\) hay \(Y[i]\) có thể được cập nhật nhiều lần.

Kết quả có thể rất lớn. Bạn chỉ cần trả về phần dư khi chia kết quả tối ưu cho \(10^9+7\).

Ví dụ

Có \(N=3\) năm, với dữ liệu ban đầu:

Mansur thu được nhiều tiền nhất bằng cách bán cả hai con ngựa vào cuối năm \(1\):

• Ban đầu có \(1\) con ngựa.
• Sau năm \(0\) có \(1 \cdot 2=2\) con.
• Sau năm \(1\) có \(2 \cdot 1=2\) con.
• Bán cả hai con, thu \(2 \cdot 4=8\).

Sau đó có \(M=1\) cập nhật: đổi \(Y[1]\) thành \(2\). Dữ liệu trở thành:

Một phương án tối ưu lúc này là bán một con sau năm \(0\), rồi ba con sau năm \(2\):

• Ban đầu có \(1\) con ngựa.
• Sau năm \(0\) có \(1 \cdot 2=2\) con.
• Bán một con, thu \(3\), còn một con.
• Sau năm \(1\) có \(1 \cdot 1=1\) con.
• Sau năm \(2\) có \(1 \cdot 3=3\) con.
• Bán ba con, thu \(3 \cdot 1=3\). Tổng tiền là \(3+3=6\).

Chi tiết cài đặt

Cho \(N\), \(X\), \(Y\) và dãy cập nhật. Trước lần cập nhật đầu tiên và sau mỗi lần cập nhật, hãy tính số tiền lớn nhất Mansur có thể thu được, lấy phần dư modulo \(10^9+7\).

Trong C hoặc C++, cài đặt các hàm trong header dùng chung horses.h:

int init(int N, int X[], int Y[]);
int updateX(int pos, int val);
int updateY(int pos, int val);

Trong Java, cài đặt các phương thức sau trong lớp horses:

public int init(int N, int[] X, int[] Y)
public int updateX(int pos, int val)
public int updateY(int pos, int val)

Hàm init(N, X, Y) được gọi đầu tiên và đúng một lần:

• N: số năm.
• X: mảng có \(N\) phần tử; X[i] là hệ số tăng trưởng năm \(i\), với \(0 \le i \le N-1\).
• Y: mảng có \(N\) phần tử; Y[i] là giá bán một con ngựa sau năm \(i\), với \(0 \le i \le N-1\).
• Hai mảng chứa dữ liệu ban đầu, trước mọi cập nhật. Sau khi init kết thúc, X và Y vẫn hợp lệ; bạn có thể thay đổi nội dung của chúng nếu muốn.
• Hàm trả về số tiền lớn nhất có thể thu được với dữ liệu ban đầu, modulo \(10^9+7\).

Hàm updateX(pos, val) thay đổi X[pos] thành val; hàm updateY(pos, val) thay đổi Y[pos] thành val. Trong cả hai hàm, \(0 \le \texttt{pos} \le N-1\). Mỗi hàm trả về số tiền lớn nhất có thể thu được sau cập nhật đó, modulo \(10^9+7\).

Mọi giá trị ban đầu và sau cập nhật của \(X[i]\), \(Y[i]\) đều thuộc đoạn \([1,10^9]\). Sau init, chương trình chấm gọi updateX và updateY tổng cộng \(M\) lần.

Chỉ nộp phần cài đặt hàm, không viết main. C và C++ đều dùng #include "horses.h"; LQDOJ cung cấp cùng tên header cho cả hai ngôn ngữ. Java dùng lớp horses, không viết phương thức main.

Phân nhóm

Mỗi subtask được trọn điểm nếu tất cả test của subtask đều đúng, nếu không được \(0\) điểm. Test mẫu là pretest \(0\) điểm.

Chương trình chấm mẫu

Chương trình chấm mẫu đọc tệp horses.in:

• Dòng \(1\): N.
• Dòng \(2\): X[0] ... X[N-1].
• Dòng \(3\): Y[0] ... Y[N-1].
• Dòng \(4\): M.
• Các dòng \(5,\ldots,M+4\): type pos val; type=1 tương ứng với updateX, type=2 tương ứng với updateY.

Chương trình in giá trị trả về của init, tiếp theo là giá trị trả về của từng lần gọi updateX hoặc updateY, mỗi giá trị trên một dòng. Grader trên LQDOJ dùng đầu vào/đầu ra chuẩn thay cho tệp, giữ nguyên giao diện hàm.

Dữ liệu vào:

3
2 1 3
3 4 1
1
2 1 2

Kết quả:

8
6