방출 스펙트럼

행성과 별자리 성간 협의회(ICPC)의 과학자들은 천체가 내는 방출 스펙트럼을 분석해 천체의 구성 성분을 연구한다. 천체의 방출 스펙트럼은 원자 에너지 전이로 방출된 전자기파의 진동수 분포와 그 복사의 세기를 함께 나타낸 것이다. 다시 말해 천체가 내는 빛에서 각 색의 세기가 얼마인지를 기록한다.

양자역학의 가정에 따르면 천체의 방출 스펙트럼은 항상 불연속이다. 그래서 ICPC는 스펙트럼을 정수 수열로 저장한다. 수열의 각 자리는 특정 파장의 세기이고, 수가 클수록 방출 세기가 크다. 수열에서 이웃한 자리는 스펙트럼에서 이웃한 파장에 대응한다.

방출 스펙트럼은 아주 복잡한 물리 과정의 결과라서 천체의 수명 동안 변한다. 특히 아직 완전히 밝혀지지 않은 원자 반응 때문에 어느 순간 이웃한 두 파장의 세기가 서로 뒤바뀔 수 있다.

과학자들은 한 천체의 스펙트럼을 특정 파장 구간에서 아주 자세히 관측하고 있다. 파장 구간과 정수 $K$가 주어질 때, 그 구간에서 $K$번째로 작은 세기가 얼마인지 알고 싶어 한다. 과학자들의 질문과 스펙트럼에서 일어난 세기 교환이 뒤섞인 관측 기록이 주어진다. 모든 질문에 답하라.

첫째 줄에 측정한 파장의 개수 $N$과 사건의 개수 $Q$가 주어진다 ($1 \le N, Q \le 10^5$). 둘째 줄에 $N$개의 정수 $I_1, I_2, \dots, I_N$이 주어진다. $I_i$는 $i$번째 파장의 처음 세기이다 ($0 \le I_i \le 10^9$).

다음 $Q$개의 줄은 각각 사건 하나를 나타내고, 사건의 종류를 뜻하는 문자로 시작한다. 과학자의 질문은 문자 Q로 시작하고, 원자 반응에 의한 세기 교환은 문자 S로 시작한다.

질문 줄은 문자 뒤에 세 정수 $A$, $B$, $K$가 온다. $A$번 자리부터 $B$번 자리까지의 파장 중에서 $K$번째로 작은 세기를 묻는다 ($1 \le A \le B \le N$, $1 \le K \le B - A + 1$).

교환 줄은 문자 뒤에 정수 $W$가 하나 온다. $W$번 자리와 $W + 1$번 자리의 세기를 서로 바꾼다 ($1 \le W \le N - 1$).

질문마다 한 줄에 정수 하나를 출력한다. $A$번 자리부터 $B$번 자리까지의 파장 중에서 $K$번째로 작은 세기이다. 질문은 입력에 나온 순서대로 답한다.