Hôm nay zxa sẽ đố các bạn thí sinh của Contest11 một bài toán khá là DỄ. Zxa có một dãy số nguyên độ dài n. Zxa sẽ thực hiện m truy vấn. Có ba loại truy vấn có dạng:

• 1 x v - thay đổi ax = v (1≤ x ≤ n, |v|≤100000).

• 2 l r – in ra đoạn con liên tiếp có tổng lớn nhất bắt đầu từ i và kết thúc ở j với mọi l≤ i ≤ j ≤ r. 

• 3 k – trả về dãy a sau khi thực hiện thao tác thứ k. Với k = 0 tức là về lại dãy ban đầu.

Dữ liệu vào: 

- Dòng đầu tiền gồm 1 số nguyên dương n (n <= 10^5).

- Dòng tiếp theo là dãy số nguyên a gồm n số ( |𝑎𝑖| ≤100000).

- Dòng thứ ba gồm 1 số nguyên dương m (m≤100000).

- M dòng tiếp theo mỗi dòng là 1 loại thao tác.

Dữ liệu ra:

- Gồm nhiều dòng, mỗi dòng là câu trả lời của truy vấn loại 2 là tổng của đọan con tìm được.