P8796 [Lanqiao Cup 2022 National AC] Replace Characters

Given a string $s$ that contains only lowercase English letters, each operation chooses an interval $[l_i, r_i]$ and replaces all letters $x_i$ in this interval of $s$ with the letter $y_i$. After all operations are completed, output the resulting string.

The first line contains a string $s$. The second line contains an integer $m$. The next $m$ lines each contain $4$ parameters $l_i, r_i, x_i, y_i$, separated by a single space. Here $l_i, r_i$ are integers, and $x_i, y_i$ are lowercase letters.

Output one line containing a string representing the answer.

**【Scale and Constraints of testdata】** - For $40\%$ of the testdata, $|s|, m \leq 5000$. - For all testdata, $1 \leq |s|, m \leq 10^5$, $1 \leq l_i \leq r_i \leq |s|$, $x_i \neq y_i$, where $|s|$ denotes the length of the string $s$. Lanqiao Cup 2022 National Contest Group A Problem H (Group C Problem J). Translated by ChatGPT 5