Flag Dance

Sangheon, who does nothing but code every day, felt his brain was steeped only in code, so he decided to go see a flag dance performance to engage his mind in a different direction. In the flag dance performance, N performers stand in a line and wave their flags with force. Each performer holding a flag has a charisma value ci, so some performers wave their flags more rhythmically than others.

While watching the flag dance, Sangheon noticed that some consecutive performers waved their flags alternately. He named this an 'alternating flag dance'. An alternating flag dance is the motion in which performers L through R each wave their flag to the left or to the right. A performer whose distance from performer L is even, including performer L, waves the flag to the left, and a performer whose distance is odd waves it to the right, then returns the flag to the body. Here, the distance between performer x and performer y is |x - y|.

Unable to escape from problem solving, Sangheon decided to call the absolute value of the difference between the sum of the charismas of the performers who waved their flags to the left and the sum of the charismas of the performers who waved their flags to the right in an alternating flag dance the uniformity of the alternating flag dance. A large uniformity means one side feels overwhelmingly more charismatic than the other, so it may look asymmetric. Sangheon believes the uniformity of an alternating flag dance carries important meaning. Also, since the performers waving flags are swept up by the heat of the performance and momentary mistakes, their charismas can increase or decrease. Considering all these situations, Sangheon now wants to find the uniformity of every alternating flag dance. Let us help Sangheon!

The first line gives the natural number N, the number of performers in the flag dance, and the natural number Q, the number of situation changes, separated by a space. (1 ≤ N ≤ 300,000, 1 ≤ Q ≤ 300,000)
The second line gives the integers c1, c2, ..., cN separated by spaces, where ci is the charisma of the i-th performer. (-100,000 ≤ ci ≤ 100,000)
From the third line, across Q lines, three integers are given in one of the following forms separated by spaces.\

• 1 L R : The alternating flag dance consisting of performers L through R is performed. (1 ≤ L ≤ R ≤ N)\
• 2 L x : The charisma of performer L increases by the integer x. (1 ≤ L ≤ N, -100,000 ≤ x ≤ 100,000)
  It is guaranteed that at least one query of the first kind (the form '1 L R') is given.

For each query of the first kind, print the uniformity of the corresponding alternating flag dance on its own line.