Problem : 226 - K. CP

Problem Statistics

Solved Member: 14　　Submission: 465　　User Tried: 22

Statement:

CP = copy and paste

翰翰無事去學測考場 CP 回來了，最近無聊的在家裡滾來滾去。

每當他無聊的時候就會打開記事本，在上面一直重複複製跟貼上的動作。

更詳細一點來說，記事本上起初有一個字串 S，以編號 0 代表最前面的字母。翰翰做了 n 次操作，每一次操作將字串 [l,r] 的範圍複製，並且將這次複製的字串貼上在第 x 個字母之前(若 x = 目前字串長度代表貼在整個字串最後面)，貼上之後若字串的長度 > m，翰翰會將後面的字母全部刪掉，讓 S 的長度為 m。他希望知道做完所有操作之後，整個字串會變成什麼？

Input:Output:

每個測試檔只有一筆測試資料。
第一行為一個整數 m。第二行是一個字串 S，第三行是一個整數 n。
接著 n 行每一行有 3 個整數，分別為 l,r,x ，以空格分隔開。

限制：
1 ≤ |S| ≤ 1000000
1 ≤ n,m ≤ 1000000
0 ≤ l ≤ r < 目前字串長度
0 ≤ x ≤ 目前字串長度

10% 測資滿足：n,m ≤ 1000
40% 測資滿足：n,m ≤ 80000
S 由 a-z,A-Z,0-9 字元所組成

請輸出一行，包含一個字串，代表依序執行完所有操作後，所形成的字串。

Sample Input:Sample Output:

10
abcde
2
0 4 0
0 9 1

aabcdeabcd

HINT:

原字串：abcde
第一次操作完：abcdeabcde
第二次操作完：aabcdeabcdebcdeabcde，由於長度 > m，只取前 m 個字母變成 aabcdeabcd。

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1	3000ms	262144kb	10
2	6000ms	262144kb	10
3	6000ms	262144kb	10
4	6000ms	262144kb	10
5	6000ms	262144kb	10
6	6000ms	262144kb	10
7	6000ms	262144kb	10
8	6000ms	262144kb	10
9	6000ms	262144kb	10
10	45000ms	262144kb	10