According to Wikipedia,
Léon: The Professional is a 1994 English-language French action crime thriller film written and directed by Luc Besson. It stars Jean Reno and Gary Oldman, and features the motion picture debut of Natalie Portman. In the film, Léon (Reno), a professional hitman, reluctantly takes in 12-year-old Mathilda (Portman), after her family is murdered by corrupt Drug Enforcement Administration agent Norman Stansfield (Oldman). Léon and Mathilda form an unusual relationship, as she becomes his protégée and learns the hitman's trade.
Like in film, we have a professional man. His name is Liton. He is a professional tea stall manager in KUET pocket gate. Most of the boys in KUET call him ‘Liton Mama’.
One day a bunch of boys went to Liton : The Professional and requested to reduce the prices of the commodities (biscuits, juices, cakes etc) of the tea stall. As the Mama is very professional he decided to change the prices of the commodities in a certain manner.
There are N commodities in the tea stall. Liton : The Professional can offer Q queries to the boys. Each query can have one of the three operations given below.
1 l r x : Update Ai with Ai + x * (-1)i - l from l to r.
2 l r x : Update Ai with Ai + x * (-1)i - l + 1 from l to r.
3 l r x : Sum of Ai where l <= i <= r.
Where Ai is the ith commodity of the tea stall of Liton : The Professional.
Input
The first line of the input contains N and Q. The number of the elements in the array.
The next line contains N space separated integers.
Each of the next Q lines contain a query of the form type l r.
Constraints
1 ≤ N ≤ 200000
1 ≤ Q ≤ 200000
1 ≤ type ≤ 3
1 ≤ L ≤ R ≤ N
Output
For each of type 3 queries print the desired output.
Sample
| Input | Output |
|---|---|
10 5 1 2 3 4 5 6 7 8 9 10 3 1 5 1 1 5 2 3 1 5 2 9 10 5 3 8 10 | 15 17 27 |
