Pyy now is in the third year of college and he has a lot of spare time to have fun. So he joined the school photography community

There is a line of trees by the HUST East Ninth Road (hai). Every day when pyy pass a section of the road he will choose the most beautiful line of trees to take pictures.

But because of the weather, every tree is not the same in every day. So pyy scores each tree, and he will dynamically modify the score.

There are multiple sets of data

For each set of data:

The first line, two integers N and M  represent the total number of trees and the total number of operations (taking pictures or modifying the score)respectively.

The next N lines, each row an integer, is the score of the tree given by pyy at the beginning.

The next M lines, three integers per line. The first integer K is 1 or 2.

K = 1 means that pyy passes through a section of the road and is ready to take pictures. The next two integers a and b give the range of the selected park (1≤a, b≤N), a may be greater than b.

K = 2 means that pyy modified the score of a tree, the next two integers p and s, says that the score of the p-th tree is changed to s(1 ≤ p ≤ N).

Among them, 1 ≤ N ≤ 500000, 1 ≤ M ≤ 100000, all scoring is an absolute value of not more than 1000 integer.

Each time Pyy pass a section of the road will correspond to one line output, contains only one integer, said the max sum of the score of the trees selected by pyy.

Note: As pyy want to practice his skill, so every time he pass the road will at least take photo of one tree, even if the tree is not beautiful.

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

2
-1