{"code":"ezlol","name":"Liên Minh Dễ Dàng","description":"[user:cuom1999] đang đánh Liên Minh Huyền Thoại với vị tướng tủ soilehpa. [user:cuom1999] đã đánh từng trận một. Mỗi trận có một hệ số phong độ là $a_i$. Nếu phong độ gánh team của [user:ami] không nhỏ hơn $a_i$, [user:cuom1999] sẽ chiến thắng ván đấu đó. Cứ mỗi một ván thắng, phong độ của [user:ami] lại tăng lên đúng $a_i$. Hiện tại, có $n$ trận đấu, với các chỉ số phong độ lần lượt là $a_1$, $a_2$, ..., $a_n$, [user:cuom1999] muốn cho [user:ami] tập tạ, nên sẽ có $q$ truy vấn, mỗi truy vấn thuộc 2 loại sau :\r\n\r\n1.  [user:cuom1999] thay đổi hệ số phong độ của trận đấu $i$ thành $x$\r\n\r\n2. [user:cuom1999] hỏi xem nếu [user:ami] lần lượt đánh các trận từ $l$ đến $r$ thì cần phong độ ban đầu tối thiểu (trước khi đánh) là bao nhiêu để chắc chắn thắng tất cả các trận đấu đó.\r\n\r\nVí dụ : Nếu [user:ami] cần thắng các trận có chỉ số phong độ lần lượt là $1, 2, 3$ thì [user:ami] cần ít nhất 1 điểm phong độ trước khi đánh. Sau trận đầu tiên, [user:ami] sẽ có phong độ là $1 + 1 = 2$, đủ để thắng trận 2. Sau trận thứ hai, [user:ami] sẽ có phong độ là $2 + 2 = 4$, và dễ dàng chiến thắng trận 3.\r\n\r\nVì [user:ami] đang bận gánh team, các bạn sẽ thay [user:ami] trả lời câu hỏi này.\r\n\r\n####Input\r\n- Dòng đầu chứa 2 số nguyên dương $n$ và $q$.\r\n\r\n- Dòng tiếp theo chứ n số nguyên dương $a_1$, $a_2$, ..., $a_n$ là chỉ số phong độ của ván đấu.\r\n\r\n- q dòng cuối cùng có dạng sau:\r\n\r\n- `1 i x` : [user:cuom1999] thay $a_i$ = $x$ $(0 \\leq x \\leq 10^9,$ $1 \\leq i \\leq n)$\r\n\r\n- `2 l r` : [user:cuom1999] muốn hỏi xem [user:ami] cần ít nhất bao nhiêu điểm phong độ để lần lượt thắng các trận đấu $a_l$, $a_{l+1}$, ..., $a_r$ $(1 \\leq l \\leq r \\leq n)$.\r\n\r\n#### Output\r\n- Với mỗi truy vấn 2, in ra kết quả.\r\n\r\n- Dữ liệu đảm bảo luôn có ít nhất một truy vấn loại 2.\r\n#### Scoring\r\n- Trong tất cả các test, $1 \\leq x, a_i \\leq 10^9$ , $1 \\leq i \\leq n$.\r\n- Subtask $1$ ($20\\%$ số điểm): $2 \\leq n , q \\leq 1000$.\r\n- Subtask $2$ ($40\\%$ số điểm): $2 \\leq n , q \\leq 100000$, và không có truy vấn loại 1.\r\n- Subtask $3$ ($40\\%$ số điểm): $2 \\leq n , q \\leq 300000$.\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 3\r\n        1 2 3\r\n        2 1 2\r\n        1 1 3\r\n        2 1 3 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        3\r\n        ```\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        10 10\r\n        1 2 3 4 5 6 7 8 9 10\r\n        2 1 2\r\n        1 1 3\r\n        2 1 3\r\n        1 5 20\r\n        1 6 1000\r\n        2 1 7\r\n        2 1 5\r\n        2 1 10\r\n        1 3 69\r\n        2 2 7 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        3\r\n        968\r\n        8\r\n        968\r\n        905\r\n        ```\r\n    ??? warning \"Note\"\r\n\r\n        - Truy vấn 1, dãy phong độ là 1 2. [user:ami] cần 1 điểm phong độ để thắng tất cả ván đấu.\r\n        - Truy vấn 2, dãy phong độ là 3 2 2. [user:ami] cần 3 điểm phong độ để thắng tất cả ván đấu.\r\n        - Cảm ơn bạn [user:Toilaaibanbietko7A4] đã truyền ý tưởng cho mình.","points":600.0,"partial":true,"time_limit":2.0,"memory_limit":1048576,"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}}