{"code":"22_tht_sokhao_bc_4","name":"Biến đổi xâu","description":"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}$\r\n \r\nChuỗ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$.\r\n\r\n**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.\r\n\r\n####Input\r\n- 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;\r\n- Dòng thứ hai chứa số $m$ $(1 \\leq m \\leq 1.5 \\times 10^5)$\r\n- $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)$\r\n\r\n#### Output \r\nGhi ra thiết bị ra chuẩn xâu $s$ sau biến đổi.\r\n\r\n## Scoring \r\n- Có $20$% số test ứng với $20$% số điểm của bài có $n, m \\le 2000$;\r\n- 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$;\r\n- Có $20$% số test khác ứng với $20$% số điểm của bài có $n \\leq 3 \\times 10^5$;\r\n- 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'$;\r\n- 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\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        aaaabbbbcccc\r\n        3\r\n        0 2 a y\r\n        5 9 b c\r\n        1 3 a z\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        yyyzbccccccc\r\n        ```\r\n    ??? warning \"Note\"\t\r\n        - Sau bước 1 xâu $s$ là **yyy**abbbbcccc\r\n        - Sau bước 2 xâu $s$ là yyyab**ccccc**cc\r\n        - Sau bước 3 xâu $s$ là y**yyz**bccccccc","points":1900.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}