{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003ePhù thủy huyền bí thường có khả năng thông qua ba phương pháp thông thường: sở hữu nó như một tài năng bẩm sinh, học hỏi và thực hành để có được nó, hoặc nhận được từ một sinh vật khác, thường là một vị thần, linh hồn, hoặc quỷ nào đó. Một số pháp sư được miêu tả có một tài năng đặc biệt khiến họ nổi bật so với đa số nhân vật trong thế giới huyền bí không thể học phép thuật.\u003cbr\u003e\u003cbr\u003ePhù thủy, pháp sư, pháp sư, pháp sư, và những người hành phép bằng các danh hiệu khác đã xuất hiện trong thần thoại, truyện dân gian và văn học suốt lịch sử ghi chép, với các tác phẩm huyền bí lấy cảm hứng từ nền văn hóa này.\u003cbr\u003e\u003cbr\u003eTrong văn học hiệp sĩ thời trung cổ, phù thủy thường xuất hiện dưới hình dạng một người đàn ông già khôn ngoan và đóng vai trò như một người hướng dẫn, với Merlin trong câu chuyện về vua Arthur là một ví dụ điển hình. Những phù thủy khác có thể xuất hiện dưới hình dạng kẻ ác, thù địch với anh hùng.\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/1e46bbeb5f1edd92de4f3dd0ffad9d7c?v\u003d1706325350\"\u003e\u003c/center\u003e \u003cbr\u003e\u003cbr\u003eÔng Zstu là một phù thủy, ông có nhiều chú lùn giống như dobby, mỗi chú đều có một sức mạnh ma thuật (có thể là tiêu cực). Một ngày nọ, ông Zstu muốn thử nghiệm khả năng của mình trong việc thực hiện một số phép thuật. Ông bắt các chú lùn đứng thành một hàng thẳng, từ vị trí 1 đến vị trí n, và ông sử dụng hai loại phép thuật, phép thuật Thay đổi và phép thuật Truy vấn, loại đầu tiên là thay đổi sức mạnh của một chú lùn, loại thứ hai là lấy tổng lớn nhất của chuỗi con đẹp trong một đoạn cho trước. Một chuỗi con đẹp là một chuỗi con mà tất cả các cặp liền kề của chú lùn trong chuỗi có vị trí chẵn lẻ khác nhau. Bạn có thể làm điều tương tự như ông Zstu không?\u003cbr\u003e \u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Dòng đầu tiên là một số nguyên T đại diện cho số lượng bài kiểm tra.\u003cbr\u003eMỗi bài kiểm tra bắt đầu bằng hai số nguyên n, m đại diện cho số lượng chú lùn và số lần ông Zstu sử dụng phép thuật.\u003cbr\u003e(n, m \u0026lt;\u003d 100000)\u003cbr\u003eDòng tiếp theo có n số nguyên đại diện cho sức mạnh phép thuật của các chú lùn, sức mạnh phép thuật nằm trong khoảng từ -1000000000 đến 1000000000.\u003cbr\u003eTiếp theo là m dòng, mỗi dòng có ba số nguyên như sau \u003cbr\u003eloại a b mô tả một phép thuật.\u003cbr\u003eNếu loại bằng 0, bạn nên đầu ra tổng lớn nhất của chuỗi con đẹp trong đoạn [a, b].(1 \u0026lt;\u003d a \u0026lt;\u003d b \u0026lt;\u003d n)\u003cbr\u003eNếu loại bằng 1, bạn nên thay đổi sức mạnh phép thuật của chú lùn tại vị trí a thành b.(1 \u0026lt;\u003d a \u0026lt;\u003d n, 1 \u0026lt;\u003d b \u0026lt;\u003d 1e9)\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Đối với mỗi truy vấn loại 0, đầu ra câu trả lời tương ứng."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n1 1\r\n1\r\n0 1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}