String Equivalence Relations

You are given three lowercase alphabet strings a, b and target. Strings a and b have the same length and are defined to be equivalent: a[i] = b[i]. For example, if a = "abc" and b = "xyz", then "a" = "x", "b" = "y" and "c" = "z".

Also, we can make the following kinds of inferences for characters:

• c = c
• a = b implies b = a
• a = b and b = c implies a = c

Return the smallest lexicographically equivalent string for target.

Constraints

• n ≤ 1,000 where n is the length of a and b
• m ≤ 1,000 where m is the length of target

https://binarysearch.com/problems/String-Equivalence-Relations

Examples

Example 1

Input

• a = axc
• b = xdz
• target = ddxz

Output

• answer = aaac

Explanation

We know that "a" = "x" and "x" = "d", so "a" = "d". So we can replace the "d"s and "x" with "a"s. Then we can directly replace "z" with "c".

Example 2

Input

• a = abc
• b = def
• target = xyz

Output

• answer = xyz

Explanation

There’s no inferences we can make here.

Solution