456. Game of Sorting

0

Medium

Alex needs to rearrange a string based on a predetermined order. He has two strings, 'order' and 's'. The 'order' string contains unique characters that were previously sorted in a specific order. The task is to permute the characters in 's' so that they match the order specified in the 'order' string. In other words, if character 'x' appears before character 'y' in the 'order' string, then 'x' should appear before 'y' in the permuted string. If there are any characters in 's' that are not present in the 'order' string, they should be sorted in alphabetical order. Print the permutation of 's' that satisfies these conditions.

Input Format

The first line contains the 'order' string. The second line contains the 's' string.

Output Format

The string 's' sorted according to the given 'order'.

Example

Input

cba abcd

Output

cbad

Constraints

1 <= N <= 104
Loading...

View Submissions

Console