12741번 - 쓰담쓰담

카이스트에는 신입생이 N명이 들어왔다. 그들에게는 1부터 N까지의 번호가 붙어있고, i번째 사람의 키는 A_i이다. 처음에 신입생은 번호순으로 일렬로 차례로 서 있다. 강한필은 신입생을 X번 쓰다듬으려고 한다. 그가 한 번 신입생을 쓰다듬을 때 L번째 사람부터 R번째 사람까지 쓰다듬는다. (L과 R은 쓰다듬을 때마다 바뀐다.)

그는 신입생을 쓰다듬을 때 부드럽게 쓰다듬기를 원하기 때문에 L ≤ j < R을 만족하는 정수 j에 대하여 j+1번째 사람의 키가 j번째 사람의 키보다 작지 않기를 원한다. 그렇지 않으면 강한필이 쓰다듬을 때에 화를 낼 것이다. 몇몇 신입생들은 쓰다듬어지기를, 몇몇은 그렇지 않기를 원하기 때문에, 신입생들은 중간에 L번째 사람과 R번째 사람이 Y번 자리를 바꾼다. (L과 R은 자리를 바꿀 때마다 바뀔 수 있다.) 신입생들의 수와 키, 강한필이 쓰다듬는 정보, 신입생들이 자리를 바꾼 정보가 주어질 때, 강한필이 쓰다듬을 때마다 화를 내는지 내지 않는지 출력하여라.

첫째 줄에 문제에서 주어진 N(1 ≤ N ≤ 100000)과 X+Y (1 ≤ X + Y ≤ 100000)과 공백을 사이에 두고 주어진다.

둘째 줄에는 키를 나타내는 N개의 정수 A_i (1 ≤ A_i ≤ 10⁹)가 주어진다.

그 이후 X+Y개의 줄에는 공백을 사이에 둔 3개의 자연수가 주어지고, Q, L, R이라 하자. (Q = 1 또는 2, 1 ≤ L ≤ R ≤ N)

Q가 1이면 강한필이 L번째 사람부터 R번째 사람까지 쓰다듬는다는 뜻이고, Q가 2이면 L번째 사람과 R번째 사람이 서로 자리를 바꾼다는 뜻이다.

출력은 X개의 줄로 이루어져 있다.

i번째 줄에, 강한필이 i번째로 신입생을 쓰다듬을 때, 화를 낸다면 “HSS090”을, 화를 내지 않는다면 “CS204”를 출력한다.