LEXSTR - Lexicographically Smallest

no tags 

Taplu and Abhishar loved playing scrabble. One day they thought of inventing a new game using alphabet tiles. Abhishar wrote a string using tiles and gave a set of pairs (i,j) to Taplu. Pair “i, j” (0 based indexing) means that Taplu can swap the i’th and j’th tile in the string any number of times.  He then asks Taplu to give the lexicographically smallest string that can be produced by doing any number of swaps on the original string.

Input

First line contains T(1<=T<=10), the number of testcases.

First line of each test case contains the initial string S. Length of Sttring is len(1<=len<=100000).

Next line contains the number of pairs M (1<=M<=100000).

Next M lines contains pairs i j that means ith character can be swapped with jth character.

Note - i and j can be same and same i,j pair can occur twice.

 

Output

For each testcase output the lexicographically smallest string that can be made from the initial string.

Example

Input:

1
lmaf
3
0 1
1 2
2 3 Output: aflm
Suppose you are given a string of length n and a set of pairs(i, j such that 0 <= i < j < n). Pair “i, j” (0 based indexing) means that you can swap the i’th and j’th character in the string any number of times. You have to output the lexicographically smallest string that can be produced by doing any number of swaps on the input string.

hide comments
AMIT KUMAR YADAV: 2016-07-28 15:56:23

Last edit: 2016-07-28 16:15:57

Added by:Rajesh Kumar
Date:2014-09-20
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64