Atomic Energy Observations

Dr. XiaoCheng has just obtained an unusual meteorite sample from the research institute and is eager to observe it. Under the view of precise instruments, every atom composing the meteorite is visible with high clarity. He notices that these atoms are arranged in several columns, each having a highly similar structure. Dr. XiaoCheng decides to focus on a single column of atoms.

This chosen column initially contains \(N\) atoms arranged in order, where the \(i\)th atom has energy \(E_i\). As time passes and tests are performed, the observed column undergoes two kinds of changes:

• merge x e: Merge the current \(x\)th atom and the \((x+1)\)th atom into a new atom with energy \(e\).
• insert x e: Insert a new atom with energy \(e\) between the current \(x\)th atom and the \((x+1)\)th atom.

Dr. XiaoCheng is particularly interested in the range difference of any contiguous subinterval (with at least 2 atoms) of the column. For a given subinterval, its range difference is defined as the difference between the maximum and minimum energy values in that subinterval. He periodically performs two types of queries:

• max x y: Considering the atoms from the current \(x\)th to the \(y\)th atom (inclusive), compute the maximum possible range difference among all contiguous subintervals (of length at least 2). It can be shown that this is equal to \(\max(E_x, E_{x+1}, \ldots, E_y) - \min(E_x, E_{x+1}, \ldots, E_y)\).
• min x y: Considering the same range of atoms from \(x\) to \(y\), compute the minimum possible range difference among all contiguous subintervals (of length at least 2). Observing that any contiguous subinterval of length 2 has a range difference of \(|E_i - E_{i+1}|\), the answer is the minimum of all adjacent differences in the interval \(x\) to \(y\).

Your task is to process a sequence of operations (both modifications and queries) on the column and output the answer for each query.

Note: All indices are 1-indexed.

inputFormat

The first line contains two integers \(N\) and \(M\), representing the initial number of atoms and the number of operations, respectively.

The second line contains \(N\) integers \(E_1, E_2, \ldots, E_N\), where \(E_i\) is the energy of the \(i\)th atom.

Each of the following \(M\) lines contains an operation in one of the following formats:

• merge x e
• insert x e
• max x y
• min x y

It is guaranteed that the operations are valid. For merge and insert operations, \(x\) indicates the position of the atom (1-indexed) and the new atom is merged with or inserted after the \(x\)th atom.

outputFormat

For each query operation (max or min), output a single line containing the corresponding answer.

sample

5 7
3 8 6 7 2
max 1 5
min 1 5
merge 2 5
min 1 4
insert 2 4
max 1 5
min 2 4

6
1
2
5
1

</p>