시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 8 8 8 100.000%

문제

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

具体的な仕様は次のとおりである.初め,ファイルの内容は文字列 S である.引き続いて,コピー&ペー ストの操作が N 回行われる.i 回目の操作は,位置 Ai から位置 Bi までの文字列を複写し,複写された文 字列を元の文字列の位置 Ci に挿入貼付する,というものである.ここで,位置 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) には,整数 Ai, Bi, Ci が空白を区切りとして書かれている.これ は,i 回目の操作は位置 Ai から位置 Bi までの文字列を複写し位置 Ci に挿入貼付する,というもので あることを表す.

출력

標準出力に,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 回目の操作の直前の文字列の長さを Li とすると,0 ≦ Ai < Bi ≦ Li および 0 ≦ Ci ≦ Li (1 ≦ i ≦ N).

예제 입력 1

2 18
copypaste
4
3 6 8
1 5 2
4 12 1
17 18 0

예제 출력 1

ac

この例では,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 を得る.

よって,操作後の文字列 acyppypastoopyppyp の先頭 K = 2 文字である ac を出力する.

예제 입력 2

6 100
jjooii
3
5 6 2
4 6 1
1 2 3

예제 출력 2

joioji