시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 14 3 2 40.000%

문제

창영이는 새로운 게임을 만들었다.

이 게임을 하려면 먼저 종이에 양의 정수 N개를 써야 한다. 같은 정수를 두 번 쓸 수 없으며, 1보다 크거나 같고 N보다 작거나 같아야 한다. 이제 연속된 부분 구간을 골라서 왼쪽이나 오른쪽으로 회전시킬 수 있다. (5, 1, 8, 3)을 왼쪽으로 한 번 회전시키면 (1, 8, 3, 5)가 되고, 오른쪽으로 한 번 회전시키면 (3, 5, 1, 8)이 된다. 또, 수열의 특정 위치에 있는 수가 무엇인지 자기 자신에게 물어볼 수도 있다.

즉, 배열은 다음과 같은 세 가지 연산을 수행할 수 있다.

  1. A부터 B까지 구간을 왼쪽으로 K번 회전시킨다. (L a b k)
  2. A부터 B까지 구간을 오른쪽으로 K번 회전시킨다. (R a b k)
  3. X번째 숫자는 무엇일까? (P x)

1번과 2번 연산의 조건은 1 ≤ a < b ≤ N, 1 ≤ k < b-a+1 이며, 3번 연산의 조건은 1 ≤ x ≤ N 이다.

(P x)연산이 주어졌을 때마다 답을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 100,000)과 연산의 개수 Q (1 ≤ Q ≤ 100,000)이 주어진다.

둘째 줄에는 처음 배열에 들어있는 N개의 양의 정수가 주어진다.

다음 Q개 줄에는 문제에 나와있는 형식대로 연산이 하나씩 주어진다.

출력

3번 명령이 주어질 때 마다 x번째 위치에 있는 수를 출력한다.

예제 입력 1

7 5
7 5 3 1 4 2 6
L 1 3 2
R 2 4 1
P 1
P 4
P 7

예제 출력 1

3
5
6
W3sicHJvYmxlbV9pZCI6IjMwOTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzggXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViODI0XHViYTc0IFx1YmEzY1x1YzgwMCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBOXHVhYzFjXHViOTdjIFx1YzM2OFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWI5N2MgXHViNDUwIFx1YmM4OCBcdWM0ZjggXHVjMjE4IFx1YzVjNlx1YzczY1x1YmE3MCwgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwIE5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzgxYyBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViZDgwXHViZDg0IFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWFjZThcdWI3N2NcdWMxMWMgXHVjNjdjXHVjYWJkXHVjNzc0XHViMDk4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKDUsIDEsIDgsIDMpXHVjNzQ0IFx1YzY3Y1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWQ1NWMgXHViYzg4IFx1ZDY4Y1x1YzgwNFx1YzJkY1x1ZDBhNFx1YmE3NCAoMSwgOCwgMywgNSlcdWFjMDAgXHViNDE4XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVkNTVjIFx1YmM4OCBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYTRcdWJhNzQgKDMsIDUsIDEsIDgpXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHViNjEwLCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkMmI5XHVjODE1IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YmIzNFx1YzVjN1x1Yzc3OFx1YzljMCBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwXHVjNWQwXHVhYzhjIFx1YmIzY1x1YzViNFx1YmNmYyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5ODksIFx1YmMzMFx1YzVmNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzEzOCBcdWFjMDBcdWM5YzAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkFcdWJkODBcdWQxMzAgQlx1YWU0Y1x1YzljMCBcdWFkNmNcdWFjMDRcdWM3NDQgXHVjNjdjXHVjYWJkXHVjNzNjXHViODVjIEtcdWJjODggXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE4XHViMmU0LiAoTCBhIGIgayk8XC9saT5cclxuXHQ8bGk+QVx1YmQ4MFx1ZDEzMCBCXHVhZTRjXHVjOWMwIFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgS1x1YmM4OCBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYThcdWIyZTQuIChSIGEgYiBrKTxcL2xpPlxyXG5cdDxsaT5YXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWJiMzRcdWM1YzdcdWM3N2NcdWFlNGM/IChQIHgpPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+MVx1YmM4OFx1YWNmYyAyXHViYzg4IFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDAgMSAmbGU7IGEgJmx0OyBiICZsZTsgTiwgMSAmbGU7IGsgJmx0OyBiLWErMSBcdWM3NzRcdWJhNzAsIDNcdWJjODggXHVjNWYwXHVjMGIwXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0MCAxICZsZTsgeCAmbGU7IE4gXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4oUCB4KVx1YzVmMFx1YzBiMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjXHViOWM4XHViMmU0IFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiAoMiAmbGU7IE4gJmxlOyAxMDAsMDAwKVx1YWNmYyBcdWM1ZjBcdWMwYjBcdWM3NTggXHVhYzFjXHVjMjE4IFEgKDEgJmxlOyBRICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2M5OFx1Yzc0YyBcdWJjMzBcdWM1ZjRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBRXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM4MWNcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMjk0IFx1ZDYxNVx1YzJkZFx1YjMwMFx1Yjg1YyBcdWM1ZjBcdWMwYjBcdWM3NzQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4zXHViYzg4IFx1YmE4NVx1YjgzOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjIFx1YjljOFx1YjJlNCB4XHViYzg4XHVjOWY4IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDkzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUklOR0lcdTAxNjBQSUwiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIHdhbnRlZCB0byBzcGluIG9uIGEgc3Bpbm5lciB0b2RheSwgYnV0IG91dHNpZGUgcHJldHR5IGJhZCByYWluIHN0YXJ0ZWQgYW5kIGhlIGRlY2lkZWQgdG8gc3RheSBpbiBoaXMgaG91c2UuIFRoZXJlZm9yZSwgaGUgaW52ZW50ZWQgbmV3IGdhbWUgd2hpY2ggaGUgaW50ZW5kZWQgdG8gcGxheSB3aG9sZSBkYXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZpcnN0LCBvbiBvbmUgcGllY2Ugb2YgcGFwZXIgaGUgd3JvdGUgTiBkaWZmZXJlbnQgcG9zaXRpdmUgaW50ZWdlcnMgYmV0d2VlbiAxIGFuZCBOLiBOb3csIGhlIGNhbiBjaG9vc2UgYW55IGludGVydmFsIG9mIHN1YnNlcXVlbnQgZWxlbWVudHMgYW5kIHJvdGF0ZSBpdCBsZWZ0IG9yIHJpZ2h0LiBFeGFtcGxlLCBpZiAoNSwgMSwgOCwgMykgaXMgdGhlIGludGVydmFsLCB0aGVuIGFmdGVyIG9uZSBsZWZ0IHJvdGF0aW9uIGhlIGdldHMgKDEsIDgsIDMsIDUpLiBTaW1pbGFyLCB3aXRoIG9uZSByaWdodCByb3RhdGlvbiBoZSBnZXRzICgzLCA1LCAxLCA4KS4gQmVzaWRlIHJvdGF0aW5nIGNob29zZW4gaW50ZXJ2YWxzLCBNaXJrbyBjYW4gYXNrIGhpbSBzZWxmIHdoaWNoIG51bWJlciBpcyBvbiBzcGVjaWZpYyBwb3NpdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U28sIHRoZXJlIGFyZSB0aHJlZSBkaWZlcmVudCBvcGVyYXRpb24gb24gdGhlIGFycmF5OiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkludGVydmFsIGZyb20gcG9zaXRpb24gQSB0byBCIE1pcmtvIHJvdGF0ZXMgSyB0aW1lcyB0byB0aGUgbGVmdC4gT3BlcmF0aW9uOiBMIGEgYiBrJm5ic3A7PFwvbGk+XHJcblx0PGxpPkludGVydmFsIGZyb20gcG9zaXRpb24gQSB0byBCIE1pcmtvIHJvdGF0ZXMgSyB0aW1lcyB0byB0aGUgcmlnaHQuIE9wZXJhdGlvbjogUiBhIGIgayZuYnNwOzxcL2xpPlxyXG5cdDxsaT5NaXJrbyBhc2sgaGltIHNlbGYgd2hpY2ggbnVtYmVyIGlzIGF0IHBvc2l0aW9uIFggaW4gY3VycmVudCBhcnJheS4gT3BlcmF0aW9uOiBQIHgmbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Gb3IgMS4gYW5kIDIuIG9wZXJhdGlvbiBjb25zdHJhaW50cyBhcmUgMSAmbGU7IGEgJmx0OyBiICZsZTsgTiwgdGUgMSAmbGU7IGsgJmx0OyBiICZuZGFzaDsgYSArIDEuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciAzLiBvcGVyYXRpb24gY29uc3RyYWludCBpcyAxICZsZTsgeCAmbGU7IE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlbHAgTWlya28gYW5kIGFzayBmb3IgaGltIHdoaWNoIG51bWJlciBpcyBhdCBwb3NpdGlvbiBYIGZvciBldmVyeSBvcGVyYXRpb24gUCB4LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIE4gKDIgJmxlOyBOICZsZTsgMTAwIDAwMCkgYW5kIFEgKDEgJmxlOyBRICZsZTsgMTAwIDAwMCksIHNpemUgb2YgYXJyYXkgbmEgbnVtYmVyIG9mIG9wZXJhdGlvbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gcG9zaXRpdmUgaW50ZWdlcnMuIFRoaXMgbGluZSByZXByZXNlbnRzIGFycmF5IGF0IHRoZSBiZWdpbmluZyBvZiB0aGUgZ2FtZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TmV4dCBRIGxpbmVzIHJlcHJlc2VudCBvcGVyYXRpb25zIGluIGRlc2NyaWJlZCBmb3JtYXQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGV2ZXJ5IDMuIGNvbW1hbmQgKFAgeCkgd3JpdGUgc2luZ2xlIGludGVnZXIgb24gYSBsaW5lIHdoaWNoIHJlcHJlc2VudHMgd2hpY2ggbnVtYmVyIGlzIGF0IHBvc2l0aW9uIHguPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d