F. HKDATA

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Dữ liệu tài chính của một công ty trong n ngày được biểu diễn bằng một dãy số t_1, t_2,…,t_n trong đó t_i\ (1≤i≤n) là dữ liệu cho ngày thứ i , nếu t_i≥0 tức là ngày i công ty thu về t_i đồng, ngược lại t_i < 0 tức là ngày i công ty phải chi |t_i| đồng. Lãnh đạo công ty thường thống kê số liệu về tổng thu chi của một dãy ngày liên tiếp mà có biến động lớn nhất, mức đánh giá biến động từ ngày L đến ngày R được tính bằng |∑_{i=L}^R t_i| .

Một nhân viên đã truy cập trái phép dữ liệu của công ty trước khi lãnh đạo thống kê số liệu, nhân viên đã thay đổi số liệu của một dãy các ngày liên tiếp từ ngày u đến ngày v\ (1≤u≤v≤n) một lượng c , cụ thể với ngày i\ (u≤i≤v) giá trị t_i đã được thay đổi thành t_i+c . Sau khi thống kê số liệu xong, nhân viên này sẽ thay đổi lại dữ liệu như ban đầu.

Yêu cầu: Cho biết dữ liệu ban đầu là t_1, t_2,…,t_n q giả định thay đổi số liệu, với mỗi giả định hãy cho biết giá trị |∑_{i=L}^R t_i| lớn nhất với 1≤L≤R≤n .

Dữ liệu:

  • Dòng đầu chứa hai số nguyên dương n,q ;
  • Dòng thứ hai chứa n số nguyên t_1, t_2,…,t_n\ (|t_i|≤10^9) ;
  • Dòng thứ k\ (1≤k≤q) trong q dòng sau, mỗi dòng chứa ba số nguyên mô tả giả định thay đổi số liệu u,v,c\ (1≤u,v≤n;|c|≤10^9) .

Kết quả:

  • Gồm q dòng, mỗi dòng chứa một số nguyên là giá trị mà lãnh đạo công ty thống kê tương ứng với giả định trong file dữ liệu vào.

Ví dụ:

Dữ liệu:

5 2
1 -1 2 1 1
2 2 -2
2 4 -2

Kết quả:

4
4

Giới hạn:

  • Subtask \#1: ( 30\% số điểm): 1 ≤ n, q ≤ 20 ;
  • Subtask \#2: ( 30\% số điểm): 1 ≤ n, q ≤ 5000 ;
  • Subtask \#3: ( 30\% số điểm): 1 ≤ n, q ≤ 10^5, 0\le v-u \le 20 ;
  • Subtask \#4: ( 10\% số điểm): 1 ≤ n, q ≤ 10^5 .