Master of the Shell Game

Given a string, perform T swaps of characters at the given 0-indexed positions in order and print the final string.

Easy2StringSimulationImplementationInterviewNo attempts yetTime limit1sMemory limit128 MB

Problem

Younghoon is so skilled at the shell game that he can find the hidden ball with his eyes closed. To trick him, you will play a shell game with a string instead of cups.

Given a string SS, apply TT swaps in order and print the result. Each swap exchanges the character at position AA of SS with the character at position BB.

Input

The first line contains the string SS. Its length is at least 11 and at most 100100, and it consists only of uppercase and lowercase English letters and hyphens (-).

The second line contains the number of swaps TT, where 1T501 \le T \le 50.

Each of the following TT lines contains two integers AA and BB separated by a space. AA and BB are integers with 0A,B<S0 \le A, B < |S|, where the first character of the string is position 00.

Output

Print the final string after applying all TT swaps, on one line.