Kstar has found a new dodgeball club called the Anonymous Dodgeball Association (or ADA). The ADA loves laces, but more importantly, they love dodgeball, so let's focus on that.

The ADA has ~N~ members, who each have a unique ID from ~1~ to ~N~. Person ~i~ has a dodgeball skill level of ~A[i]~. Some people are so bad that their skill level is negative.

There are two types of meetings: training meetings and game meetings.

At a training meeting, everyone practices and has fun. No one takes it seriously. As a result, exactly one member's skill level will change. In other words, for some ~i~ and some ~v~, ~A[i]~ will change to ~v~.

At a game meeting, every member comes and lines up in increasing order of their ID (~1, 2, 3, \dots, N~). Then the coach comes and numbers them off into ~t~ teams, numbered from ~1~ to ~t~. The number of teams changes from meeting to meeting.

The coach always numbers them off as follows:

1. The coach walks down the line from Person ~1~ to Person ~N~.
2. She starts by putting Person ~1~ in Team ~1~.
3. For every person after, she puts them in the team that comes after the previous person's team, except if the previous person is in Team ~t~, in which case she wraps around to Team ~1~.

For example, if there are ~7~ people and ~3~ teams, the coach would number them off as such:

The skill level of a team is defined as the sum of the skill levels of the members of that team.

Kstar's official opinion on the ADA is ewww exercise, so she decides to join as an executive instead of a member. As the head of the Fairness Committee at ADA, Kstar's job is to make sure that no team is too strong.

In order to gather information, Kstar attends ~Q~ meetings. Every game meeting, she notices that the coach has numbered everyone off into ~t~ teams, and she want to know specifically the skill level of Team ~x~. The values of ~t~ and ~x~ change from meeting to meeting. She must also take into account the changes in skill level caused by training meetings. At each training meeting, for some ~i~ and ~v~, ~A[i]~ is set to ~v~.

Since Kstar would much rather be watching the games instead of tediously adding numbers, can you write a program to help her?

Constraints

• ~1 \leq N, Q \leq 100~ ~000~
• ~-10~ ~000 \leq A[i], v \leq 10~ ~000~
• For game meetings, ~1 \leq x \leq t \leq N~

Subtasks

Subtask 1 [30%]

There are no training meetings, and Kstar will only ask for the skill level of Team 1.

Subtask 2 [30%]

There are no training meetings.

Subtask 3 [40%]

No further constraints.

Input Specification

The first line of input will contain ~N~ and ~Q~.

The second line of input will contain ~N~ numbers: ~A[1]~, ~A[2]~, ~\dots~, ~A[N]~.

For the next ~Q~ lines of input, the first character is either a T, indicating a training meeting or a G, indicating a game meeting.

If it is a T, two numbers follow: ~i~ and ~v~, indicating that the skill level of Member ~i~ has their skill level changed to ~v~. In other words, ~A[i]~ is changed to ~v~.

If it is a G, two numbers follow: ~t~ and ~x~, indicating that the coach has numbered everyone off into ~t~ teams, and you must output the skill level of Team ~x~.

Output Specification

For every game meeting, output the corresponding answer.

Sample Input

7 4
2 3 5 7 11 13 17
G 2 1
G 2 2
T 2 10
G 3 2

Sample Output

35
23
21

Explanation For Sample

The first line of input tells us that there are ~7~ people, and ~3~ meetings you attend. The skill levels of the members are ~2~, ~3~, ~5~, ~7~, ~11~, ~13~, and ~17~, respectively.

• In the first meeting, the ADA is arranged into ~2~ teams. Team ~1~ has Person ~1~, ~3~, ~5~, and ~7~, who respectively have skill levels of ~2~, ~5~, ~11~, and ~17~. Their sum is ~35~.
• In the second meeting, the ADA is arranged into ~2~ teams. Team ~2~ has Person ~2~, ~4~, and ~6~, who respectively have skill levels of ~3~, ~7~, and ~13~. Their sum is ~23~.
• In the third meeting, Person ~2~'s skill level becomes ~10~.
• In the fourth meeting, the ADA is arranged into ~3~ teams. Team ~2~ has Person ~2~ and Person ~5~, who respectively have skill levels of ~10~ and ~11~. Their sum is ~21~.