Ban đầu nội dung tệp là xâu \(S\). Có \(N\) thao tác. Thao tác \(i\) sao chép đoạn từ vị trí \(A_i\) đến ngay trước vị trí \(B_i\), rồi chèn bản sao tại vị trí \(C_i\). Vị trí \(x\) là khe ngay sau \(x\) ký tự đầu tiên, nên vị trí 0 ở đầu xâu và vị trí bằng độ dài ở cuối xâu. Các chỉ số trong thao tác đều được hiểu trên xâu trước thao tác.

Nếu sau khi chèn, độ dài vượt quá \(M\), các ký tự bên phải bị xóa cho đến khi còn đúng \(M\) ký tự. Hãy tìm \(K\) ký tự đầu sau tất cả thao tác.

Dữ liệu vào

• Dòng 1: \(K,M\).
• Dòng 2: xâu ban đầu \(S\).
• Dòng 3: \(N\).
• \(N\) dòng tiếp: \(A_i,B_i,C_i\).

Dữ liệu ra

In \(K\) ký tự đầu của xâu cuối cùng.

Ràng buộc

• \(1\le K\le200,\quad1\le M\le10^9,\quad1\le N\le200\,000\).

\(S\) chỉ gồm chữ thường a đến z, và

• \(K\le |S|\le\min(M,200\,000)\).

Nếu \(L_i\) là độ dài ngay trước thao tác \(i\) thì

• \(0\le A_i<B_i\le L_i,\qquad0\le C_i\le L_i\).

Phân nhóm

• Nhóm 1 (10 điểm): \(M,N\le2000\).
• Nhóm 2 (90 điểm): không có ràng buộc bổ sung.

Ví dụ

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

ac

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

joioji