AROPE3 - Alphabetic Rope3

The Alphabetic Rope is now available in the market. The Alphabetic Rope consists of alphabetic characters in each stripe which looks like string. You are given an Alphabetic Rope consisting of lowercase alphabetic characters. You have to perform some operations on the rope and answers some queries on it. Queries are of 3 types:

  • 1 X Y: Cut the rope segment from X to Y and Reverse it then join at the front of the rope.
  • 2 X Y: Cut the rope segment from X to Y and Reverse it then join at the back of the rope.
  • 3 Y: Print on a new line the character at Yth position of the current rope.

Input

There is only one input. Input begins with single line giving Alphabetic Rope as a string S. Next line contains Q, following Q lines giving Queries as mentioned above. (Index used are 0-based)

Output

For each query of type 3, print a single character in a new line.

Constraints

1 <= |S| <= 100000. (Length of string)

1 <= Q <= 100000. (Number of queries)

Example

Input:
gautambishal
5
1 3 5
3 0
3 3
2 2 4
3 9

Output:
m
g
a

Added by:BISHAL GAUTAM
Date:2016-11-24
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:MySelf

hide comments
2017-05-26 18:02:05 lu
simple problem. useg c++ stl rope<char>
2017-01-28 15:52:30
@BISHAL GAUTAM can you see my code and tell why it is giving SIGABRT error. Source code: 18658661
2017-01-04 22:22:09 rainy jain
@BISHAL GAUTAM what is the expected complexity for reverse operation?


Last edit: 2017-01-04 22:26:56
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.