17716번 - Copy and Paste 2 서브태스크다국어

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

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

あなたの任務は，エディタのテストのため，N 回の操作後に得られる文字列の最初の K 文字を予め求め ておくことである．

整数 K，文字列の長さの上限 M，初めの文字列 S，操作の回数 N および N 回のコピー＆ペーストの操 作の指示が与えられたとき，操作後の文字列の最初の K 文字を求めるプログラムを作成せよ．

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

• 1 行目には，整数 K, M が空白を区切りとして書かれている．K は出力する文字数を表し，M は文字 列の長さの上限を表す．
• 2 行目には，文字列 S が書かれており，初めの文字列を表す．
• 3 行目には，整数 N が書かれており，操作の回数を表す．
• 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には，整数 A_i, B_i, C_i が空白を区切りとして書かれている．これ は，i 回目の操作は位置 A_i から位置 B_i までの文字列を複写し位置 C_i に挿入貼付する，というもので あることを表す．

標準出力に，N 回の操作後の文字列の最初の K 文字を 1 行で出力せよ．

• 1 ≦ K ≦ 200．
• 1 ≦ M ≦ 1 000 000 000．
• S の各文字は英アルファベットの小文字 (‘a’ – ‘z’) である．
• K ≦ (S の長さ) ≦ min{M, 200 000}．
• 1 ≦ N ≦ 200 000．
• i 回目の操作の直前の文字列の長さを L_i とすると，0 ≦ A_i < B_i ≦ L_i および 0 ≦ C_i ≦ L_i (1 ≦ i ≦ N)．

• M ≦ 2 000．
• N ≦ 2 000．

追加の制限はない．