“Hamlet: Thou wretched, rash, intruding fool, farewell. I took thee for thy better. Take thy fortune. Thou find’st to be too busy is some danger” (Shakespeare, 3.4.37-39)

As Hamlet’s mother, Gertrude, consults him on his change in attitude, Hamlet discovers who he believes to be King Claudius hidden behind curtains. After stabbing them, Polonius, father of Scolar Lartes and Ophelia, falls out deceased. The more time Hamlet spends on the path of revenge, the crazier his actions and thoughts seem to become. During the start of his revenge, he still believes in justifying the ghost’s claims. Later, he ignores that logical step, resulting in the murder of Polonius as he does not confirm King Claudius’s identity behind the curtains. Hamlet justifies his actions through the annoyance Polonius had caused by meddling in his business, compared to my experience with others, seems completely insane as his action and reasoning do not equal. This event further shows how Hamlet currently only uses emotions and urges to control his actions, proving that the id has increased control over Hamlet as he remains fixated on revenge.

Hamlet has a list of people he wants out of his world, referred to by unique numbers, but his mind often changes. Therefore the priority for each person constantly changes with new people being added and removed (changing the value of someone from 0 or their value to 0). Hamlet has constructed this so that groups formed by these people commonly consist of people representing consecutive numbers. Therefore, he will ask you the value of groups in multiple ranges ~L~ to ~R~.

Input specifications

The first line contains integer ~N~, ~(1 \le N \le 10^5)~ representing the max number of people that can be on Hamlet’s list followed by ~Q~, ~(1 \le Q \le 10^5)~ representing the number of queries.

The next line contains ~N~ numbers, ~a_i~ ~(0 \le a_i \le 10^5)~ representing the initial value for each person that can be on the list. 0 means they are not on the list.

The next ~Q~ lines are the queries, ~T~ ~(0 \le T \le 5)~, ~P~ ~(1 \le P \le N)~, ~V~ ~(0 \le V \le 10^5)~, ~L~ and ~R~ ~(1 \le L \le R \le N)~.

Queries will follow this format starting with a character representing the type of query.

• S T The following ~T~ lines will include integers L R, output the total sum of all values within the ~T~ ranges of people (the ~T~ ranges will not overlap)
• C P V Change the value of person ~P~ to ~V~

Output specifications

For each C query, print the sum of values for all ranges of people listed

Sample input 1

5 5
0 0 5 3 1
S 1
2 4
C 1 2
S 2
1 1
4 5
C 4 0
S 1
1 5

Sample output 1

8
6
8