Copy and Paste(コピー&ペースト) - joi2012-day4

出典: 第11回日本情報オリンピック 日本代表選手選考会

時間制限: 17秒

メモリ制限: 512MB

テキストエディタの最も重要な機能の 1 つとして,コピー&ペースト (複写・貼付) がある.JOI 社は,コピー&ペーストを非常に高速に処理するテキストエディタの開発を開始した.JOI 社に所属する優秀なプログラマであるあなたは,核となるコピー&ペーストの処理の実装の担当となった.JOI 社の命運が懸かっているので,何としても正確かつ高速なプログラムを作成したい.

具体的な仕様は次のとおりである.初め,ファイルの内容は文字列 S である.引き続いて,コピー&ペーストの操作が N 回行われる.i 回目の操作は,位置 A_i から位置 B_i までの文字列を複写し,複写された文字列を元の文字列の位置 C_i に挿入貼付する,というものである.ここで,位置 x とは,文字列の先頭から x 個の文字をたどった直後の箇所を表す (位置 0 は文字列の先頭である).ただし,操作後に文字列の長さが M を超えた場合,長さが M になるまで文字列の右端から順に文字が削除される.N 回の操作後に得られる文字列を求めたい.

課題

文字列の長さの上限 M,初めの文字列 S,操作の回数 N および N 回のコピー&ペーストの操作の指示が与えられたとき,操作後の文字列を出力するプログラムを作成せよ.

制限

1 \leqq M \leqq 1\,000\,000 文字列の長さの上限
1 \leqq N \leqq 1\,000\,000 操作の回数

入力

標準入力から以下の入力を読み込め.

出力

標準出力に,N 回の操作後の文字列を 1 行で出力せよ.

採点基準

入出力例

入力例1 出力例1
18
copypaste
4
3 6 8
1 5 2
4 12 1
17 18 0
acyppypastoopyppyp

この例では,N = 4 回のコピー&ペーストの操作は以下のように行われる.

入力例2 出力例2
100
joi
3
0 1 0
3 4 3
2 3 3
jjooii