ZS the Coder is the CEO of the Text Editor company. This year, the company has decided to make a special text editor for animals. After all, it's time for animals to have a text editor made specially for them.
ZS the Coder has hired Fluffy the squirrel and Flippy the bird, who was looking for a job as a software engineer. ZS the Coder said : "Our users will have the ability to insert a string s. According to my research, animals use a different type of keyboard compared to humans like me. So, sometimes they might accidentally shift their fingers to the wrong position, and every letter 'a' becomes the letter 'b', 'b' becomes 'c', ..., and 'z' becomes 'a'. Thus, our software needs to have the ability to perform cyclic shifts of a substring of s. For example, suppose s = "zscoder". Then, if we perform a cyclic shift on the substring [1, 4] once (the substring is 1-indexed), then z becomes a, s becomes t, c becomes d and o becomes p. So, the new string is s = "atdpder". Thus, your job is to code a program that enables the users to perform cyclic shifts on a substring [l, r] c times, where c is a number of their choice." The two new workers quickly went on to code the software.
In less than a week, they have finished the software! After they released it, however, a few users complained that the classic cut-and-paste operation is not supported. ZS the Coder told Fluffy and Flippy in their weekly meeting : "We have received many complaints from users who were furious that they can't perform the cut-and-paste operation, which is supported in human software like Notepad. We MUST implement this operation. More formally, the user can select a substring [l, r] and a position pos. After that, the substring [l, r] will be cut and it will be pasted after position pos. (note that the position is counted after the substring has been cut) For example, consider the string s = "fluffy". Suppose we have [l, r] = [3, 5] and pos = 3. Then, the substring "uff" is cut and pasted after the character 'y' (note that positions are 1-indexed), which results in s = "flyuff". Note that if pos = 0, then the substring will be pasted before the first character of the string. Now, hurry up and get this feature done or I'll fire you two tomorrow!"
Finally, after 12 hours of continuous coding, they finally finished the feature. They published the update of the software. Flippy and Fluffy thought their work is done, until one day, ZS the Coder called them to hold an emergency meeting. He said : "Recently, many users are complaining that they can't reverse a substring and they said they'll use the text editor that was recently released by our main competitor, "Chris the Baboon Company". Their text editor support our operations and also supports the substring reverse operation! This is an emergency and you need to figure out how to implement this feature fast! More formally, the user should be able to choose a substring [l, r] and you have to reverse the substring. For example, when s = "flippy", then reversing the substring [3, 5] should change it to s = "flppiy". Now go and implement this operation before you two lose your job!"
Flippy and Fluffy sighed but managed to implement this feature and impress ZS the Coder. The text editor for animals is finally becoming the most popular text editor in the world. However, this didn't stay very long. The evil Chris has hacked into the Text Editor company and has deleted the code of the software. When Flippy and Fluffy came to work next morning, they realized to their horror that their code is gone! They had no backup and the boss is coming to the office in 1 hour! They asked for your help to code a new text editor that supports the same operations as above before their boss arrive or else they will lose their jobs! Can you help them?
The first line contains a string s, denoting the string that the user enters. The next line contains a single integer, Q, denoting the number of operations the customer has to perform. The next Q lines describes an operation. The first integer t describes the type of operation. If t = 1, three integers l, r, pos follow. This denotes that the substring [l, r] should be cut and pasted after position pos. If t = 2, then three integers follow, l, r, c, denoting that the user wants to perform a cyclic shift to the substring [l, r] c times. If t = 3, then two integers l, r follow. This means the user wants to reverse the substring [l, r].
s contains only lowercase English letters.
Your code should output a single string, which is the string s after performing all Q operations.
1 ≤ Q ≤ 100000
1 ≤ Length of s ≤ 100000
Subtask 1 (5 points) : 1 ≤ Length of s, Q ≤ 3000
Subtask 2 (9 points) : There are only operations of type 2.
Subtask 3 (31 points) : There are only operations of type 1.
Subtask 4 (25 points) : There are no operations of type 3.
Subtask 5 (30 points) : Original Constraints
1 3 6 3
2 1 4 5
3 2 8
3 4 7