You are given a string s and should process m queries. Each query is described by two 1-based indices l_{i}, r_{i} and integer k_{i}. It means that you should cyclically shift the substring s[l_{i}... r_{i}] k_{i} times. The queries should be processed one after another in the order they are given.

One operation of a cyclic shift (rotation) is equivalent to moving the last character to the position of the first character and shifting all other characters one position to the right.

For example, if the string s is abacaba and the query is l_1 = 3, r_1 = 6, k_1 = 1 then the answer is abbacaa. If after that we would process the query l_2 = 1, r_2 = 4, k_2 = 2 then we would get the string baabcaa.


-----Input-----

The first line of the input contains the string s (1 ≤ |s| ≤ 10 000) in its initial state, where |s| stands for the length of s. It contains only lowercase English letters.

Second line contains a single integer m (1 ≤ m ≤ 300) — the number of queries.

The i-th of the next m lines contains three integers l_{i}, r_{i} and k_{i} (1 ≤ l_{i} ≤ r_{i} ≤ |s|, 1 ≤ k_{i} ≤ 1 000 000) — the description of the i-th query.


-----Output-----

Print the resulting string s after processing all m queries.


-----Examples-----
Input
abacaba
2
3 6 1
1 4 2

Output
baabcaa



-----Note-----

The sample is described in problem statement.

Difficulty: interview

Starter code:

Solutions:
s=input()
def shift(x,k):
    x=x[-k:]+x[:-k]
    return x
for i in range(int(input())):
    l,r,k=tuple(map(int,input().split()))
    l-=1
    k%=(r-l)
    s=s[:l]+shift(s[l:r],k)+s[r:]
print(s)


"""
Codeforces Educational Round

Problem 598 B Queries on a String

@author yamaton
@date 2015-11-12
"""

import itertools as it
import functools
import operator
import collections
import math
import sys

def cycle_shift(s, k):
    n = len(s)
    k %= n
    return s[(n-k):] + s[:(n-k)]

def solve(triples, s, m):
    for (l, r, k) in triples:
        s = s[:l-1] + cycle_shift(s[l-1:r], k) + s[r:]
    return s

def p(*args, **kwargs):
    return print(*args, file=sys.stderr, **kwargs)

def main():
    s = input()
    m = int(input())
    triples = [tuple(int(c) for c in input().strip().split()) for _ in range(m)]

    result = solve(triples, s, m)
    print(result)


def __starting_point():
    main()

__starting_point()

s = input()
m = int(input())
for it in range(m):
	l, r, k = [int(i) for i in input().split()]
	l -= 1
	k = k % (r - l)
	s = s[:l] + s[r - k: r] + s[l: r - k] + s[r:]
print(s)

word = input()
N = int(input())

query = []
for i in range(N):
    q = input().split()
    query.append(list(map(int, q)))

for q in query:
    l, r, k = q[0] - 1, q[1] - 1, q[2]
    k = k % (r - l + 1)
    if l == r or k == 0:
        continue
    word = word[0:l] + word[r-k+1:r+1] + word[l:r-k+1] + word[r+1:]

print(word)

s = input()
n = int(input())
for i in range(n):
    l, r, k = map(int, input().split())
    ds = k % (r - l + 1)
    s = s[:l - 1] + s[r - ds: r] + s[l - 1: r - ds] + s[r:]

print(s)

S = [ c for c in input() ]
Q = int(input())
for _ in range(Q):
  l, r, s = map(int, input().split())
  length = r-l+1
  s %= length
  S = S[:l-1] + S[r-s:r] + S[l-1:r-s] + S[r:]
print("".join(S))

#!/usr/bin/env python3

s = input()
m = int(input())

for i in range(m):
    l, r, k = [int(x) for x in input().split()]
    start = s[:l-1]
    middle = s[l-1:r]
    end = s[r:]
    # shift middle k times
    ln = r-l+1
    k %= ln
    middle_e = middle[:ln-k]
    middle_s = middle[ln-k:]
    s = start + middle_s + middle_e + end

print(s)


string = [e for e in input()]
n = int(input())

for i in range(n):
    l, r, k = map(int, input().split())
    l -= 1
    r -= 1    
    k %= r - l + 1
    old_string = string[l:r + 1]
    for j in range(l, r + 1):
        string[j] = old_string[j - l - k]
    
print(''.join(string))

def shift( s , k ):
    #print( "shift" , s , k )
    k %= len(s)
    #print( "after shift" , s[-k:] + s[:-k] )
    return s[-k:] + s[:-k]

def process( s , l , r , k ):
    #print( "process" , s , l , r , k )
    #print( "after process" , s[:l-1] , shift( s[l-1:r] , k ) , s[r:] )
    return s[:l-1] + shift( s[l-1:r] , k ) + s[r:]

def __starting_point():

    s = input().strip()
    m = int( input() )
    for _ in range(m):
        l , r , k = [ int(x) for x in input().strip().split() ]
        s = process( s , l , r , k )
    print(s)
__starting_point()

s=input()
n=int(input())
for i in range(n):
    l,r,k=map(int,input().split())
    k%=r-l+1
    seg=s[l-1:r]
    seg=seg[len(seg)-k:]+seg[:len(seg)-k]
    s=s[:l-1]+seg+s[r:]
print(s)

# import sys
# sys.stdin = open('cf598b.in')

s = list(input())
m = int(input())

for _ in range(m):
	l, r, k = map(int, input().split())
	if l != r:
		l -= 1
		r -= 1
		k %= r - l + 1
		s[l:r+1] = s[r+1-k:r+1] + s[l:r+1-k]

print(''.join(s))

s = input()
m = int(input())
for i in range(m):
    l, r, k = map(int, input().split())
    l = l - 1
    r = r - 1
    sub = s[l : r + 1]
    k = k % len(sub)
    part1 = sub[0: len(sub) - k]
    part2 = sub[len(sub) - k : len(sub)]
    sub = part2 + part1
    s = list(s)
    s[l : r + 1] = sub[0: len(sub)]
    s = "".join(s)
print(s)

from collections import deque
s = list(input())
n = int(input())
for i in range(n):
    l,r,k = map(int,input().split())
    x = deque(s[l-1:r])
    x.rotate(k)
    s[l-1:r] = x
print(''.join(map(str,s)))

my_string = input().strip()
my_string = list(my_string)
sl = len(my_string)
m = int(input())

for i in range(m):
    l, r, k = list(map(int, input().split()))
    range_length = r - l + 1
    k = k % range_length
    l = l - 1
    k = range_length - k

    my_string[l:r] = my_string[l+k:r] + my_string[l:l+k] 

ans = ''.join(my_string)
print(ans)


s = input()
n = int(input())
for i in range(n):
    l, r, k = map(int, input().split())
    l -= 1
    r -= 1
    k %= len(s[l:r + 1])
    s = s[:l] + s[r - k + 1: r + 1] + s[l: r - k + 1] + s[r + 1:]
print(s)

def main():
    mode="filee"
    if mode=="file":f=open("test.txt","r")
    get = lambda :[int(x) for x in (f.readline() if mode=="file" else input()).split()]
    s = list(input())
    [m]=get()
    for z in range(m):
        [l,r,k]=get()
        l-=1
        if k> r-l:
            k = k%(r-l)
        temp = s[:l] + s[r-k:r] + s[l:r-k] + s[r:]
        s = temp
    print("".join(s))


    if mode=="file":f.close()


def __starting_point():
    main()

__starting_point()

from collections import deque

def solve(s,l,r,k):
    s1,s2 = s[:l - 1],s[r:]
    tmp = s[l - 1 : r]
    k %= (r - l + 1)
    d = deque(tmp)
    for _ in range(k):
        x = d[-1]
        d.pop()
        d.appendleft(x)
    tmp = ''.join(d)
    return ''.join([s1,tmp,s2])

s = input()

m = int(input())

for _ in range(m):
    l,r,k = list(map(int,input().split()))
    s = solve(s,l,r,k)

print(s)


s = input()
for it in range(int(input())):
    l, r, k = list(map(int, input().split()))
    k %= r - l + 1
    s = s[:l - 1] + s[r - k: r] + s[l - 1: r - k] + s[r:]
print(s)


def rot(s, pos):
    return s[(len(s)-pos):] + s[:(len(s)-pos)]
s = input()
x = int(input())
s = [''] + list(s)
for i in range(x):
    a, b, c = list(map(int, input().split(' ')))
    s[a:b+1] = rot(s[a:b+1], c%(b-a+1))

print(''.join(s))


s = input()
m = int(input())
for i in range(m):
    l, r, k = map(lambda x: int(x) - 1, input().split())
    k += 1
    d = r - l + 1
    k %= d
    s = s[0:l] + s[r-k+1:r+1] + s[l:r-k+1] + s[r+1:]
print(s)

s = input()
q = int(input())
for i in range(q):
    a = list(map(int , input().split()))
    l = a[0]
    r = a[1]
    k = a[2]
    s2 = s[l-1:r]
    n = len(s2)
    k = k%n
    ls = s2[:n-k]
    rs = s2[n-k:]
    s = s[:l-1]+rs+ls+s[r:]
print(s)

s = input()
a = list(range(len(s)))
m = int(input())
for i in range(m):
    l, r, k = [int(j) for j in input().split()]
    l -= 1
    k %= r - l
    a[l:r] = a[r - k: r] + a[l:r - k]
for i in a:
    print(s[i], sep = '', end = '')
print()


import sys


s = list(sys.stdin.readline())
s2 = list(s)
numQ = int(sys.stdin.readline())


for i in range(numQ):
    ls = sys.stdin.readline().split()
    l = int(ls[0]) - 1
    r = int(ls[1]) -1
    k = int(ls[2])

    diff = r - l + 1

    for j in range(0, diff):
        newpos = ((j + k) % diff) + l
        s2[newpos] = s[j + l]

    s = list(s2) 
    

sys.stdout.write("".join(s2))