In the winter of 21ZZ, after retiring, Xiao Cheng regained an interest in physics. He borrowed some experimental equipment from a research institute and spent his days studying various microscopic particles.

One day, Xiao Cheng obtained a strange meteorite sample from the institute and began observing it immediately. Under the view of precision instruments, every atom constituting the meteorite was perfectly clear. Xiao Cheng discovered that these atoms were arranged in several rows, and the structure of each row was highly similar. Therefore, he decided to measure and test a single row of atoms.

The selected row consists of $N$ atoms arranged in sequence. Initially, the $i$-th atom has energy $E_i$. As time passes and tests are conducted, this row of atoms undergoes two types 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.

For a row of atoms, Xiao Cheng is interested in the difference between the maximum and minimum energy of two atoms in any adjacent segment, which is called the interval range. Therefore, in addition to observing changes, Xiao Cheng often needs to calculate two types of data for this row of atoms:

• max x y: The maximum value of the interval range among all sub-intervals between the current $x$-th and $y$-th atoms.
• min x y: The minimum value of the interval range among all sub-intervals between the current $x$-th and $y$-th atoms.

Here, a sub-interval refers to a sub-interval with a length of at least 2.

Xiao Cheng firmly believes that this research can win the Nobel Prize in Physics. To help Xiao Cheng fulfill his wish sooner, can you help him implement the above observations and measurements?

Input

The first line contains two integers $N$ and $M$, representing the initial number of atoms and the total number of events, respectively.

The second line contains $N$ integers $E_1, E_2, \dots, E_N$, separated by spaces, representing the energy of each atom.

The next $M$ lines each contain a string and two integers, describing an event, with the format as described in the problem statement.

Output

Output several lines, representing the measurement results of each max and min event in order.

Examples

Input 1

4 3
5 8 10 2
max 1 3
min 1 3
max 2 4

Output 1

5
2
8

Input 2

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

Output 2

1
2
1
5

Note

In the first example: In the interval $[1, 3]$, the range of the sub-interval $[1, 3]$ is 5, which is the maximum; the range of $[8, 10]$ is 2, which is the minimum. In the interval $[2, 4]$, the range of the sub-interval $[3, 4]$ is 8, which is the maximum.

In the second example: After the first insert event, the sequence becomes $[1, 3, 2, 3, 4, 5, 6]$; after the merge event, the sequence becomes $[2, 2, 3, 4, 5, 6]$; after the second insert event, the sequence becomes $[2, 2, 3, 4, 5, 6, 1]$.

Constraints

There are 10 test cases in total. The data scale and conventions for each test case are as follows:

For 100% of the data, $1 \le N, M \le 10^5$, $1 \le e, E_i \le 10^9$. Let $N'$ be the number of atoms at the current moment.

For merge events, $1 \le x \le N'-1$; For insert events, $1 \le x \le N'$; For max and min events, $1 \le x < y \le N'$. At any time, it is guaranteed that $N' \ge 2$.