Robot Movement Simulation

Little q has n robots initially placed on a number line. The i-th robot is at position \(a_i\) and is initially stationary. Little q stands at the origin \(0\).

After placing the robots, little q will perform a series of operations, each at a specified time. There are two types of operations:

1. Command Operation: At time \(t\), a command of the form
   \(t\ 1\ i\ d\ x\) is issued. This instructs the \(i\)-th robot (1-indexed) to move in direction \(d\) (either L for left or R for right) with speed \(x\) (i.e. it will move at \(x\) units per second in the specified direction) starting immediately. Its previous velocity is overridden.
2. Query Operation: At time \(t\), a query of the form
   \(t\ 2\) is issued. At that moment, little q wants to know the maximum distance from the origin among all robots, i.e. \(\max_{1\le i\le n} |\text{position}_i|\).

Note that between operations, every robot moves continuously at its current speed. All operations are given in non-decreasing order of their time \(t\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le 10^5)\) — the number of robots and the number of operations, respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \(|a_i| \le 10^9\) representing the initial positions of the robots on the number line.

The following \(m\) lines describe the operations in chronological order. Each operation is formatted as follows:

• t 1 i d x: At time \(t\) (an integer \(0 \le t \le 10^9\)), the \(i\)-th robot (1-indexed) is instructed to move. The direction \(d\) is either L (left) or R (right) and \(x\) (\(1 \le x \le 10^9\)) is the speed (units per second).
• t 2: At time \(t\), output the maximum absolute distance from the origin among all robots at that exact time.

It is guaranteed that the operations are given in non-decreasing order of \(t\). Initially, at time 0, all robots are stationary.

outputFormat

For each query operation, output a single line containing one integer: the maximum absolute distance from the origin among all robots at that time.

sample

3 4
0 5 -3
1 1 2 R 2
2 2
3 1 3 L 1
5 2

7
13