Cho chuỗi kí tự \(s\) có độ dài \(n\) chỉ bao gồm các kí tự in thường. Các kí tự được đánh số từ 0 đến \(n - 1\), \(s = s_0,s_1,\dots,s_{n-1}\)

Chuỗi này sẽ được áp dụng lần lượt các thao tác thay đổi \((i,j,c_1,c_2)\) là biến đổi các vị trí là kí tự \(c_1\) thành kí tự \(c_2\) trong đoạn từ \(i\) đến \(j\).

Yêu cầu: Cho biết chuỗi \(s\) ban đầu và \(m\) thao tác biến đổi, hãy đưa ra chuỗi cuối cùng sau biến đổi.

Input

• Dòng đầu chứa chuỗi \(s\) có độ dài \(n\) \((1 \leq n \leq 10^6)\), xâu \(s\) chỉ chứa kí tự thường;
• Dòng thứ hai chứa số \(m\) \((1 \leq m \leq 1.5 \times 10^5)\)
• \(m\) dòng tiếp theo mỗi dòng chứa \(i, j, c_1, c_2\) \((0 \leq i \leq j < n; c_1 \neq c_2)\)

Output

Ghi ra thiết bị ra chuẩn xâu \(s\) sau biến đổi.

Scoring

• Có \(20\)% số test ứng với \(20\)% số điểm của bài có \(n, m \le 2000\);
• Có \(20\)% số test khác ứng với \(20\)% số điểm của bài có \(n, m \leq 5 \times 10^4\);
• Có \(20\)% số test khác ứng với \(20\)% số điểm của bài có \(n \leq 3 \times 10^5\);
• Có \(20\)% số test khác ứng với \(20\)% số điểm của bài có các kí tự trong xâu và biến đổi chỉ là \('a'\) hoặc \('b'\);
• Có \(20\)% số test còn lại ứng với \(20\)% số điểm của bài không có ràng buộc gì thêm

Example

aaaabbbbcccc
3
0 2 a y
5 9 b c
1 3 a z

yyyzbccccccc