Sao chép và dán là một trong những chức năng quan trọng nhất của trình soạn thảo văn bản. Công ty JOI bắt đầu phát triển một trình soạn thảo có thể xử lý các thao tác này rất nhanh. Là một lập trình viên giỏi của công ty, bạn được giao nhiệm vụ cài đặt phần xử lý cốt lõi. Tương lai của công ty phụ thuộc vào công việc này, nên bạn cần viết một chương trình vừa chính xác vừa nhanh.

Ban đầu, nội dung tệp là xâu \(S\). Sau đó, thực hiện \(N\) thao tác sao chép và dán. Trong thao tác thứ \(i\), sao chép đoạn xâu từ vị trí \(A_i\) đến vị trí \(B_i\), rồi chèn bản sao vào vị trí \(C_i\) của xâu hiện tại.

Ở đây, vị trí \(x\) là ranh giới ngay sau \(x\) ký tự đầu tiên của xâu; vị trí \(0\) là đầu xâu. Vì vậy, đoạn được sao chép gồm \(B_i-A_i\) ký tự nằm giữa hai ranh giới \(A_i\) và \(B_i\). Các vị trí \(A_i\), \(B_i\), \(C_i\) đều được xác định trên xâu ngay trước thao tác; việc sao chép không xóa đoạn gốc.

Nếu sau khi chèn, độ dài xâu vượt quá \(M\), xóa các ký tự từ cuối xâu cho đến khi độ dài còn đúng \(M\).

Yêu cầu

Cho giới hạn độ dài \(M\), xâu ban đầu \(S\) và thông tin của \(N\) thao tác, hãy tìm xâu thu được sau tất cả các thao tác.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(M\), là giới hạn độ dài xâu.
• Dòng thứ hai chứa xâu \(S\) ban đầu.
• Dòng thứ ba chứa số nguyên \(N\), là số thao tác.
• Dòng thứ \(i+3\) (\(1 \le i \le N\)) chứa ba số nguyên \(A_i\), \(B_i\), \(C_i\), cách nhau bởi dấu cách, mô tả thao tác thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa xâu thu được sau \(N\) thao tác.

Ràng buộc

• \(1 \le M \le 1\,000\,000\).
• \(1 \le N \le 1\,000\,000\).
• \(S\) chỉ gồm các chữ cái Latin thường và có độ dài từ \(1\) đến \(M\).
• Gọi \(L_i\) là độ dài xâu ngay trước thao tác thứ \(i\). Với mọi \(1 \le i \le N\), có \(0 \le A_i < B_i \le L_i\) và \(0 \le C_i \le L_i\).

Phân nhóm

• Các bộ kiểm thử chiếm \(10\%\) tổng số điểm thỏa mãn \(M \le 100\,000\) và \(N \le 100\,000\).

Ví dụ

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

acyppypastoopyppyp

100
joi
3
0 1 0
3 4 3
2 3 3

jjooii