Find and Replace (Gold)

Bessie sử dụng trình soạn thảo văn bản với tính năng tìm-và-thay-thế. Mỗi thao tác, cô chọn một ký tự thường $c$ và thay tất cả các lần xuất hiện của $c$ bằng một xâu không rỗng $s$ gồm các ký tự thường. Bắt đầu từ xâu "a", cô thực hiện một chuỗi thao tác để tạo xâu cuối cùng $S$.

Cho chỉ số $l$ và $r$, hãy xác định xâu con $S[l\dots r]$.

Dữ liệu vào

• Dòng đầu: $l$, $r$ và số thao tác $N$
• $N$ dòng tiếp: mỗi dòng chứa ký tự $c$ và xâu $s$

Dữ liệu ra

In xâu con $S[l\dots r]$.

Ràng buộc

• $1\le l\le r\le min(|S|,{10}^{18})$
• $r-l+1\le 2\times {10}^5$
• Tổng $|s|$ qua tất cả thao tác $\le 2\times {10}^5$
• Tất cả ký tự từ 'a' đến 'z'

Ví dụ