Cyclic Shift of a Substring

Problem Description

You are given a string $s$, and you must perform $m$ tasks. Each task gives two indices $l_i, r_i$ and an integer $k_i$ (the string is $1$-indexed), meaning that you cyclically shift the substring $s[l_i \dots r_i]$ exactly $k_i$ times. Execute the given tasks one by one, in order.

The cyclic shift operation moves the last character to the first position, and shifts every other character one position to the right.

For example, suppose $s$ is abacaba. If the first task is $l_1 = 3, r_1 = 6, k_1 = 1$, the answer becomes abbacaa. Then if the next task is $l_2 = 1, r_2 = 4, k_2 = 2$, we obtain baabcaa.

Input Format

The first line contains a string $s$ consisting only of lowercase English letters.

The second line contains an integer $m$, the number of tasks.

Each of the next $m$ lines contains three integers $l_i, r_i, k_i$.

Output Format

Output the final string $s$ after performing all $m$ tasks.

Sample Input

abacaba
2
3 6 1
1 4 2

Sample Output

baabcaa

Constraints

For all data: $1 \leq |s| \leq 10000$ ($|s|$ denotes the length of $s$), $1 \leq m \leq 300$, $1 \leq l_i \leq r_i \leq |s|$, and $1 \leq k_i \leq 1000000$.