복사와 붙여넣기 2

텍스트 에디터의 가장 중요한 기능 중 하나는 복사와 붙여넣기(복사, 붙여넣기)이다. 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개 문자를 구하는 프로그램을 작성하시오.

표준 입력에서 다음 입력을 읽는다.

• 첫째 줄에는 정수 K, M이 공백을 구분으로 쓰여 있다. K는 출력할 문자 수를 나타내고, M은 문자열 길이의 상한을 나타낸다.
• 둘째 줄에는 문자열 S가 쓰여 있으며, 처음 문자열을 나타낸다.
• 셋째 줄에는 정수 N이 쓰여 있으며, 조작의 횟수를 나타낸다.
• 이어지는 N개 줄 중 i번째 줄(1 ≤ i ≤ N)에는 정수 Ai, Bi, Ci가 공백을 구분으로 쓰여 있다. 이는 i번째 조작이 위치 Ai부터 위치 Bi까지의 문자열을 복사하고 위치 Ci에 삽입하여 붙여넣는다는 것을 나타낸다.

표준 출력에 N번의 조작 후의 문자열의 처음 K개 문자를 한 줄로 출력하시오.

• 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)이다.