충돌기

물리학자들이 x, y, z 세 종류의 입자를 연구한다. 번호를 매긴 입자 $n$개를 한 줄로 세워 충돌기에 넣는다. 실험 중에는 입자 하나에 빔을 쬐는데, 이 조사를 받은 입자는 줄의 $i$번 자리에서 사라졌다가 곧바로 $j$번 자리에 다시 나타난다. 입자가 사라지면 그 오른쪽에 있는 입자의 번호가 1씩 줄고, 입자가 다시 나타나면 그 자리 오른쪽에 있는 입자의 번호가 1씩 는다. 조사를 몇 번 한 뒤 과학자들은 $k$번 자리에 어떤 입자가 있는지 알고 싶어 한다. 이 질문에 답하는 프로그램을 작성하시오.

첫째 줄에 입자의 개수 $n$과 조사와 질의를 합한 개수 $m$이 주어진다 ($1 \le n \le 1000000$, $1 \le m \le 15000$).

둘째 줄에 x, y, z로 이루어진 길이 $n$의 문자열이 주어진다.

이어지는 $m$개 줄에는 조사 또는 질의가 하나씩 주어진다. 조사를 나타내는 줄은 문자 a와 공백으로 시작하고, $[1, n]$ 범위의 정수 두 개가 뒤따른다. 첫 번째 수는 조사를 받는 입자의 시작 위치, 두 번째 수는 도착 위치이다. 질의를 나타내는 줄은 문자 q와 공백으로 시작하고, $[1, n]$ 범위의 정수 하나가 뒤따른다. 이 수는 과학자들이 궁금해하는 위치이다.

질의마다 한 줄씩, 입력에 나온 순서대로 출력한다. $i$번째 줄에는 $i$번째 질의의 답, 즉 그 자리에 있는 입자의 이름 x, y, z 중 하나를 출력한다.

조사 a $i$ $j$는 두 단계로 일어난다. 먼저 $i$번 자리의 입자가 줄에서 빠지고, 줄에는 입자가 $n - 1$개 남는다. 그다음 그 입자를 다시 넣어 입자 $n$개짜리 줄에서 정확히 $j$번 자리를 차지하게 한다. $i$와 $j$가 같으면 줄은 그대로다. 예를 들어 줄이 xyzz이고 조사가 a 1 3이면, x를 빼서 yzz가 되고 다시 넣으면 yzxz가 된다.