Có \(N\) (\(1\le N\le 2\cdot 10^5\)) chiếc xô xếp thành một chồng, trong đó chiếc xô thứ \(i\) tính từ trên xuống có sức chứa \(a_i\) gallon (\(1\le a_i\le 10^9\)). Một vòi ở phía trên chiếc xô đầu tiên rót mỗi giây một gallon sữa vào chiếc xô này. Bên dưới xô \(N\) còn có một bể chứa.

Khi một chiếc xô đạt sức chứa của nó sau \(t\) giây, vào đầu giây thứ \(t+1\), nó lật úp để đổ lượng sữa bên trong vào chiếc xô phía dưới nếu nó không phải xô cuối cùng, hoặc vào bể chứa nếu không còn xô nào bên dưới (chiếc xô trở lại trạng thái hứng sữa vào cuối giây thứ \(t+1\)). Một chiếc xô không thể hứng sữa khi đang lật úp; mọi lượng sữa chảy tới chiếc xô đó từ phía trên trong giây này đều bị mất. Ngoài ra, mọi lượng sữa vượt quá sức chứa của chiếc xô phía dưới cũng bị mất.

Hãy xử lý \(Q\) (\(1\le Q\le 3\cdot 10^5\)) truy vấn, mỗi truy vấn được mô tả bởi ba số nguyên \(i\), \(v\) và \(t\):

1. Trước tiên, gán \(a_i=v\) (\(1\le i\le N\), \(1\le v\le 10^9\)).
2. Sau đó trả lời câu hỏi sau: Giả sử tại thời điểm \(0\), tất cả các xô và bể chứa đều rỗng. Hãy xác định số gallon sữa trong bể sau \(t\) giây (\(1\le t\le 10^{18}\)).

Các cập nhật \(a_i=v\) vẫn có hiệu lực trong những truy vấn tiếp theo.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(a_1,\dots,a_N\).

Dòng tiếp theo chứa \(Q\).

Mỗi dòng trong \(Q\) dòng sau chứa ba số nguyên \(i\), \(v\) và \(t\). Điều này có nghĩa là bạn cần gán \(a_i=v\), rồi trả lời câu hỏi ứng với \(t\).

Dữ liệu ra

In đáp án của mỗi truy vấn trên một dòng riêng.

Ví dụ

3
1 1 1
30
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 2 9
1 2 10
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 2 9
2 2 10

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

2
1 2
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10

0
0
0
0
2
2
2
2
4
4

3
1 1 1
1
1 1 1000000000000000000

499999999999999999

Phân nhóm

• Test 4–5: \(N\le 10\), \(Q\le 100\) và mọi \(t\le 10^4\).
• Test 6–11: \(N\le 10^3\), \(Q\le 10^4\).
• Test 12–23: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Silver Division — bài gốc tiếng Anh “Milk Buckets”. Tác giả: Akshaj Arora. https://usaco.org/index.php?page=viewproblem2&cpid=1591