Smallest String With Swaps

You are given a string s consisting of only lowercase English letters and a list of swap operations. Each swap operation is represented by a pair of indices (a, b) indicating that you can swap the characters at positions a and b any number of times. Your task is to determine the lexicographically smallest string that can be obtained by performing these swap operations arbitrarily.

More formally, let \( s = s_0 s_1 \cdots s_{n-1} \) be a string of length \( n \) and a list of swap operations \( \{(a_i,b_i)\} \) for \( i=1,2,\dots,m \). You are allowed to swap \( s_{a_i} \) and \( s_{b_i} \) as many times as you want. Find the minimum string in lexicographical order that can be constructed by these operations.

Input/Output Format: The input is read from stdin and the output should be written to stdout.

Example:

Input:
dcab
2
0 3
1 2
Output:
bacd

</p>

inputFormat

The input consists of multiple lines:

• The first line contains the string s consisting of lowercase English letters.
• The second line contains an integer m, representing the number of swap operations.
• The following m lines each contain two space-separated integers a and b (0-indexed) denoting a swap operation between positions a and b.

Note that you should use stdin for input.

outputFormat

Output a single line containing the lexicographically smallest string obtainable after performing the allowed swap operations.

Print your result to stdout.

## sample

dcab
2
0 3
1 2

bacd

</p>