Emission Spectrum

Scientists at the Interstellar Consortium of Planets and Constellations (ICPC) study what celestial objects are made of by analyzing their emission spectrum. The emission spectrum of a celestial object is the set of frequencies of electromagnetic radiation emitted by its atomic energy transitions, together with the intensity of that radiation. It records how strong each color of the emitted light is.

By the postulates of quantum mechanics the emission spectrum of a celestial object is always discrete, so the ICPC stores a spectrum as a sequence of integers. Each position of the sequence is the intensity of one wavelength, a larger number means a stronger emission, and neighboring positions of the sequence are neighboring wavelengths of the spectrum.

An emission spectrum is the result of very complex physical processes, so it changes over the lifetime of the object. In particular, because of atomic reactions that are not yet fully understood, the intensities of two neighboring wavelengths can be swapped at some moment.

The ICPC is watching the spectrum of one celestial object very closely. Given a range of wavelengths and an integer $K$, the scientists want the intensity of the wavelength with the $K$-th smallest intensity in that range. You are given the observation log, which mixes the questions asked by the scientists with the intensity swaps that happen in the spectrum. Answer every question.

The first line contains two integers $N$ and $Q$, the number of measured wavelengths and the number of events ($1 \le N, Q \le 10^5$). The second line contains $N$ integers $I_1, I_2, \dots, I_N$, where $I_i$ is the initial intensity of the $i$-th wavelength ($0 \le I_i \le 10^9$).

Each of the next $Q$ lines describes one event and starts with a character giving the type of the event. A question from the scientists starts with the character Q, and an atomic swap reaction starts with the character S.

A question line has three integers $A$, $B$ and $K$ after that character. The scientists ask for the $K$-th smallest intensity among the wavelengths at positions $A$ through $B$, inclusive ($1 \le A \le B \le N$, $1 \le K \le B - A + 1$).

A swap line has one integer $W$ after that character. The intensities at positions $W$ and $W + 1$ are exchanged ($1 \le W \le N - 1$).

For each question print one line with a single integer, the $K$-th smallest intensity among the wavelengths at positions $A$ through $B$, inclusive. Answer the questions in the order they appear in the input.