{"code":"prefixsumqueries","name":"Prefix sum queries","description":"Cho dãy gồm $n$ số nguyên, bạn cần phải thực hiện $q$ truy vấn thuộc các loại sau:\r\n1. Cập nhật giá trị của phần tử thứ $k$ thành $u$\r\n2. Trả lời câu hỏi: Trong mọi đoạn con bắt đầu từ $a$, kết thúc tại $i (a \\le i \\le b)$ thì đoạn con có tổng lớn nhất là bao nhiêu?\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên chứa hai số nguyên $n,q$: độ dài dãy và số truy vấn\r\n- Dòng thứ hai chứa $n$ số nguyên $x_1, x_2, ..., x_n$: giá trị lúc đầu của dãy\r\n\r\nCuối cùng là $q$ dòng mô tả các truy vấn. Mỗi dòng chứa ba số nguyên `1 k u` hoặc `2 a b`\r\n\r\n

Output

\r\n\r\n- In ra đáp án của mỗi truy vấn loại $2$\r\n\r\n

Constraints

\r\nTrong tất cả các test\r\n- $1\\le n,q\\le 2⋅10^5$\r\n- $−10^9\\le x_i,u\\le 10^9$\r\n- $1\\le k\\le n$\r\n- $1\\le a\\le b\\le n$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 8 4\r\n 1 2 -1 3 1 -5 1 4\r\n 2 2 6\r\n 1 4 -2\r\n 2 2 6\r\n 2 3 4\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 5\r\n 2\r\n 0\r\n ```","points":1600.0,"partial":true,"time_limit":1.0,"memory_limit":520000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}