Problem Description

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.

Input Format

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 Format

Output one line containing a string representing the answer.

abcaaea
4
1 7 c e
3 3 e b
3 6 b e
1 4 a c

cbecaea

Hint

【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