Replace Patterns in a String

You are given a text string and a set of pattern-replacement pairs. Your task is to replace all occurrences of each pattern in the text with its corresponding replacement. The replacements should be performed sequentially in the order they are provided.

More formally, given an integer \( n \) and \( n \) pairs \( (p_i, r_i) \), and a text string \( S \), for every \( i \) from 1 to \( n \), replace every occurrence of \( p_i \) in \( S \) with \( r_i \). Output the final modified string.

Note: The matching is done using exact string matching, and replacement is global.

inputFormat

The input is read from standard input and has the following format:

1. The first line contains an integer \( n \) representing the number of pattern-replacement pairs.
2. The next \( n \) lines each contain two non-space strings separated by a space: the first is the pattern and the second is its corresponding replacement.
3. The last line contains the text string \( S \) in which the replacements are to be performed.

You can assume that the patterns and replacements do not contain spaces.

outputFormat

Output a single line to standard output containing the modified string after all replacements have been executed.

2
abc 123
def 456
abcdef defabc

123456 456123