Little Q has $n$ robots. Initially, he places them on a number line, with the $i$-th robot at position $a_i$, while he stands at the origin.

Afterward, Little Q performs several operations. He wants to command a robot to move left or right by $x$ units. However, the robots do not seem to hear his commands clearly; in fact, they move at a constant speed of $x$ units per second.

Watching his robots move further and further away, Little Q is anxious. He wants to know the distance of the robot currently furthest from him (the origin).

Specific operations and queries are described in the Input section. Note that robots do not affect each other; that is, you do not need to consider cases where two robots collide.

Input

There are $m$ events, given in chronological order.

The first line contains two positive integers $n$ and $m$.

The next line contains $n$ integers, where the $i$-th number is $a_i$, representing the initial position of the $i$-th robot (initial speed is $0$).

The next $m$ lines each start with a non-negative integer $t_i$, representing the time (in seconds) at which the event occurs. The second part is a string $S$, representing the type of operation. The number and the string are separated by a space. The subsequent input depends on the type of $S$:

1. If $S$ is "command", it is followed by two integers $k_i$ and $x_i$, indicating that Little Q has issued a command to the $k_i$-th robot. The robot's speed is reset to $x_i$ units per second in the positive direction of the number line (if $x_i$ is negative, it moves at a speed of $\lvert x_i \rvert$ units per second in the negative direction). It is guaranteed that $1 \leq k_i \leq n$.
2. If $S$ is "query", you need to output the distance of the robot currently furthest from the origin.

It is guaranteed that $t_1 \leq t_2 \leq \dots \leq t_m$.

(Note: If multiple operations occur at the same time, they are executed in the order they are read.)

Output

For each "query" operation, output one line containing an integer representing the correct answer.

When using C/C++, please use %lld for long long. Due to the large volume of data, it is recommended not to use cin/cout for input and output.

Examples

Input 1

4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query

Output 1

180
280

Note 1

When the first command is executed, the positions of the robots are: $-20, 0, 20, 100$.

When the second command is executed, the positions of the robots are: $80, 0, 20, 100$.

At the first query, the positions of the robots are: $180, 0, -80, 100$.

When the third command is executed, the positions of the robots are: $280, 0, -180, 100$.

At the second query, the positions of the robots are: $-20, 0, -280, 100$.

Constraints

Let $C$ be the number of "command" operations and $Q$ be the number of "query" operations. ($C + Q = m$)

For all events, $0 \leq t_i \leq 10^9$. For all "command" operations, $\lvert x_i \rvert \leq 10^4$.

For all robots, $\lvert a_i \rvert \leq 10^9$.

The ranges and characteristics of all test data are shown in the table below: