TheJobOverflow | String Substitution

String Substitution :

Author

Gigaliths

Difficulty Level : Medium

Submissions : 526

Asked In : Google

Marks :10

: 11 | : 3

You are given a string $$$S$$$ , and a list of strings which needs to be substituted in the input string $$$S$$$.

A substitution is a tuple $$$( L_i , R_i , subs_i ) $$$ which denotes that we need to substitute the substring $$$S[ L_i ... R_i ]$$$ with $$$subs_i$$$.

It is guaranteed that all the intervals are non-overlapping.

You must find out the modified string $$$S_m$$$ after incurring all substitutions.

Input

First line contains a string corresponding to $$$S$$$

Second line contains a single integer N corresponding to the total number of substitutions

N lines are followed containing each tuple $$$( L_i , R_i , subs_i )$$$

Contraints

$$$ 1 \le |S| \le 1000000 $$$

$$$ 1 \le L_i \le R_i \le 1000000 $$$

Output

A single string $$$ S_m $$$ which corresponds to the modified string after all substitutions.

Example

Input

Alice_saw_a_tiger
2
0 4 Bob
12 18 Cat

Output

Bob_saw_a_Cat

You need to login to view your submissions.

You need to login to view all submissions.

Language

Result : Executed

Result : Accepted

Test Cases :