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 only. You have to perform some operations on rope and answers some queries on it.

Queries are of 3 types:

• 1 X Y: Cut the rope segment from X to Y and join at the front of rope.
• 2 X Y: Cut the rope segment from X to Y and join at the back of rope.
• 3 Y: Print on a new line the character at Yth position of 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 give 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
3
3 1
2 0 5
3 0

Output:
a
b