Copy and Paste(コピー＆ペースト) - joi2012-day4
時間制限: 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 | 操作の回数 |
入力
標準入力から以下の入力を読み込め．
- 1 行目には整数 M が書かれており，文字列の長さの上限を表す．
- 2 行目には文字列 S が書かれており，初めの文字列を表す．S はアルファベットの小文字からなり，長さは 1 以上 M 以下である．
- 3 行目には整数 N が書かれており，操作の回数を表す．
- 3 + i 行目 (1 \leqq i \leqq N) には整数 A_i, B_i, C_i が空白を区切りとして書かれており，i 回目の操作は位置 A_i から位置 B_iまでの文字列を複写し位置 C_i に挿入貼付する，というものであることを表す．i回目の操作の直前の文字列の長さを L_i とすると，0 \leqq A_i < B_i \leqq L_i および 0 \leqq C_i \leqq L_i を満たす．
出力
標準出力に，N 回の操作後の文字列を 1 行で出力せよ．
採点基準
- 採点用データのうち，配点の 10% 分については，M \leqq 100\,000，N \leqq 100\,000 を満たす．
入出力例
| 入力例1 | 出力例1 |
|---|---|
| 18 copypaste 4 3 6 8 1 5 2 4 12 1 17 18 0 |
acyppypastoopyppyp |
この例では，N = 4 回のコピー＆ペーストの操作は以下のように行われる．
- 初めの文字列は copypaste である．
- 1 回目の操作では，位置 3 から位置 6 までの文字列 ypa が複写され，位置 8 に挿入貼付されることで，文字列 copypastypae を得る．
- 2 回目の操作では，位置 1 から位置 5 までの文字列 opyp が複写され，位置 2 に挿入貼付されることで，文字列 coopyppypastypae を得る．
- 3 回目の操作では，位置 4 から位置 12 までの文字列 yppypast が複写され，位置 1 に挿入貼付されることで，文字列 cyppypastoopyppypastypae を得るが，長さが M = 18 を超えているため，右端から文字が削除され，文字列 cyppypastoopyppypa を得る．
- 4 回目の操作では，位置 17 から位置 18 までの文字列 a が複写され，位置 0 に挿入貼付されることで，文字列 acyppypastoopyppypa を得るが，長さが M = 18 を超えているため，右端から文字が削除され，文字列 acyppypastoopyppyp を得る．
| 入力例2 | 出力例2 |
|---|---|
| 100 joi 3 0 1 0 3 4 3 2 3 3 |
jjooii |