Tối ưu hàm

Cho dãy gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(|a_i| \le 10^6\)) và \(m\) truy vấn. Mỗi truy vấn có một trong hai dạng:

• Loại 1 - Cập nhật: Thay đổi giá trị \(a[p] = v\).

• Loại 2 - Tối ưu hàm: Tìm giá trị lớn nhất của hàm \(f(i_1, i_2, \ldots, i_k) = c_1 \times a[i_1] + c_2 \times a[i_2] + \ldots + c_k \times a[i_k]\) với các ràng buộc:

  • \(L \le i_1 < i_2 < \ldots < i_k \le R\) (các chỉ số được chọn trong đoạn \([L, R]\)).

• \(i_j - i_{j-1} \le D\) (khoảng cách giữa hai chỉ số liên tiếp không quá \(D\)).

Yêu cầu: Thực hiện \(m\) truy vấn. Với mỗi truy vấn loại 2 in ra giá trị lớn nhất của hàm tìm được.

Input

Dữ liệu vào:

• Dòng 1: Hai số nguyên \(n, m\) (\(1 \le n, m \le 5000\)) lần lượt là số phần tử và số truy vấn.

• Dòng 2: \(n\) số nguyên \(a_1, a_2, \ldots, a_n\).

• \(m\) dòng tiếp theo, mỗi dòng là một truy vấn:

  • Loại 1 (Cập nhật): 1 p v với \(1 \le p \le n\), \(|v| \le 10^6\).

• Loại 2 (Tối ưu): 2 k L R D $c_1$ $c_2$ $\ldots$ $c_k$ với \(1 \le k, L, R, D \le n\), \(0 \le c_1 \le c_2 \le \ldots \le c_k \le 100\).

Ràng buộc:

• Có \(40\%\) số test của bài thỏa mãn \(n \le 100\), \(m \le 100\), \(k \le 3\), không có truy vấn loại 1;

• Có \(40\%\) số test của bài thỏa mãn \(n \le 1000\), \(m \le 1000\), \(k \le 5\), \(D = n\) (không giới hạn khoảng cách);

• Có \(20\%\) số test còn lại thỏa mãn \(n \le 5000\), \(m \le 5000\), \(k \le 10\).

Output

In ra

• Với mỗi truy vấn loại 2: In ra giá trị lớn nhất tìm được.

• Nếu không thể chọn đủ \(k\) phần tử thỏa mãn điều kiện: In ra ``IMPOSSIBLE''.

Example

Input:

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

Output:

28
32

Note

Truy vấn 1: \(k = 3\), \(L = 1\), \(R = 5\), \(D = 3\), \(c_1 = 1, c_2 = 2, c_3 = 4\), dãy \(a = [2, -3, 5, 1, 4]\). Chọn các chỉ số \((1, 3, 5)\) thỏa mãn \(i_2 - i_1 \le 3\), \(i_3 - i_2 \le 3\), ta được \(f = 1 \times 2 + 2 \times 5 + 4 \times 4 = 28\).

Truy vấn 2 cập nhật \(a_2 = 5\), dãy trở thành \(a = [2, 5, 5, 1, 4]\). Truy vấn 3 có cùng tham số với truy vấn 1: chọn các chỉ số \((1, 2, 3)\) ta được \(f = 1 \times 2 + 2 \times 5 + 4 \times 5 = 32\).