Thanos Finally did it. He has collected all six infinity stones and wiped out half the life of the universe by snapping his fingers.
Twelve heroes’ disappeared in the end. They are most likely to be inside the soul stone.
Thor, Iron Man, Captain America, Hulk, Ant Man, Rocket Raccoon and a few others are out there on Earth now.
All of them are now at Wakanda (Home of Black Panther). They want to make an army to fight for the Earth. They want to use the power of the "Heart Shaped Herb" to make the army strong.
They have N soldiers for the army numbered from 1 to N. They have some initial powers.
Each time they select an “Herb”, they give it to every soldier one piece of it. When a soldier takes a "Heart Shaped Herb", he gains the power of the Herb. The power of Heart Shaped Herbs are integer numbers.
Sometimes the Avengers need to know the total power of a certain group to check whether they are ready for the fight or not. The Avengers has many other important things to take care of. They don't want to waste their time by doing this calculation. They want you to do this for them.
At First, they will give you the initial power of each soldier. And each time they give them a "Heart Shaped Herb", they will let you know the power of it. And sometimes they might have ask you to report the total power of a group of soldiers.
More formally, they can ask you to do two types of jobs.
They can give you an integer P, the power of a "Heart Shaped Herb" which is now given to all the soldiers. Suppose, there are 4 soldiers with initial power [1,4,2,6]. If they give a Herb of power 5, then power of the soldiers will be [6,9,7,11].
They can give you two integers L and R and ask you to tell them the total power of the soldiers numbered from L to R. Suppose, there are 4 soldiers with current power [6,9,7,12]. And they give you L=2 and R=4. So the Output will be 9+7+12=28.
Are you up for this!!! May be You Should. After all you're getting a chance to be a part of the Avengers.
Input
The first line is the number of people in the army N and number of Queries Q(1<=N,Q<=10^5).
The next line contains N integers a1,a2,a3,…,an (1<=ai<=10^5) the initial power the army.
Each of the Next Q line contains a query.
Each Query starts with an integer T, the type of the query.
If T is 1, there will be another integer P (1<=P<=10^5), they are giving a “Heart Shaped Herb” to all the soldiers (1 to N) of power P.
If T is 2, there will be two integers L and R (1<=L<=R<=N). You need to output the total power of the people numbered from L to R.
Output
For each of the Query type 2, you need to print the total power from L to R.
Samples
| Input | Output |
|---|---|
5 5 1 2 3 4 5 2 1 5 1 5 2 1 5 1 10 2 2 3 | 15 40 35 |
| Input | Output |
|---|---|
3 5 100000 100000 100000 2 1 3 2 2 2 1 100000 2 1 3 2 3 3 | 300000 100000 600000 200000 |
