cuom1999 đang đánh Liên Minh Huyền Thoại với vị tướng tủ soilehpa. 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 ami không nhỏ hơn \(a_i\), cuom1999 sẽ chiến thắng ván đấu đó. Cứ mỗi một ván thắng, phong độ của 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\), cuom1999 muốn cho ami tập tạ, nên sẽ có \(q\) truy vấn, mỗi truy vấn thuộc 2 loại sau :

1. cuom1999 thay đổi hệ số phong độ của trận đấu \(i\) thành \(x\)

2. cuom1999 hỏi xem nếu 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 đó.

Ví dụ : Nếu ami cần thắng các trận có chỉ số phong độ lần lượt là \(1, 2, 3\) thì ami cần ít nhất 1 điểm phong độ trước khi đánh. Sau trận đầu tiên, ami sẽ có phong độ là \(1 + 1 = 2\), đủ để thắng trận 2. Sau trận thứ hai, ami sẽ có phong độ là \(2 + 2 = 4\), và dễ dàng chiến thắng trận 3.

Vì ami đang bận gánh team, các bạn sẽ thay ami trả lời câu hỏi này.

Input

• Dòng đầu chứa 2 số nguyên dương \(n\) và \(q\).

• 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.

• q dòng cuối cùng có dạng sau:

• 1 i x : cuom1999 thay \(a_i\) = \(x\) \((0 \leq x \leq 10^9,\) \(1 \leq i \leq n)\)

• 2 l r : cuom1999 muốn hỏi xem 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)\).

Output

• Với mỗi truy vấn 2, in ra kết quả.

• Dữ liệu đảm bảo luôn có ít nhất một truy vấn loại 2.

Scoring

• Trong tất cả các test, \(1 \leq x, a_i \leq 10^9\) , \(1 \leq i \leq n\).
• Subtask \(1\) (\(20\%\) số điểm): \(2 \leq n , q \leq 1000\).
• Subtask \(2\) (\(40\%\) số điểm): \(2 \leq n , q \leq 100000\), và không có truy vấn loại 1.
• Subtask \(3\) (\(40\%\) số điểm): \(2 \leq n , q \leq 300000\).

Example

3 3
1 2 3
2 1 2
1 1 3
2 1 3 

1
3

10 10
1 2 3 4 5 6 7 8 9 10
2 1 2
1 1 3
2 1 3
1 5 20
1 6 1000
2 1 7
2 1 5
2 1 10
1 3 69
2 2 7 

1
3
968
8
968
905