Lexicographically minimal string
/

## Arrays and Strings, Data Structures, Disjoint Data Structures, Disjoint Set, Disjoint set, Graphs

Problem
Editorial
Analytics

You are given three strings named as $A$$B$, and $C$. Here, the length of the strings $A$ and $B$  is equal. All strings contain lowercase English letters. The string $A$ and $B$ contain the following properties:

1. The characters located at the same indexes in the string $A$  and $B$ are equivalent to each other.
2. If character $a$ is equivalent to character $b$ , then the character $b$ is also equivalent to the character $a$.
3. If character $a$ is equivalent to character $b$ and character $b$ is equivalent to character $c$, then character $a$ is also equivalent to character $c$.
4. Every character is equivalent to itself.

For example:

You are given two strings:

• $A - abc$
• $B - xcd$

Here, the character $a$ is equivalent to the character $x$, character $b$ is equivalent to the character $c$, and character $c$ is equivalent to the character $d$. According to the third property, the character $b$ is also equivalent to the character $d$.

You can replace any character of string $C$ with its any equivalent character. By replacing any character of the string $C$ with its equivalent characters, you can construct multiple new strings. Your task is to print the lexicographically smallest string out of all possible new strings that you can construct.

Note: If the first character of $s(s_1)$ is smaller than the first character of $t(t_1)$, then the lexicographical order is an order relation where string $s$ is smaller than string $t$. If they are equivalent, the second character is checked and so on.

Input format

• First line: String $A$
• Second line: String $B$
• Third line: String $C$

Output format

Print the lexicographically smallest string.

Constraints

$1\leq$ length of strings $A,B,C \leq 100000$

length of string $A$ = length of string $B$

All the strings consist of lowercase English letters.

SAMPLE INPUT
abc
xyz
yzp
SAMPLE OUTPUT
bcp
Explanation

In string $C$ , you can replace $y$ with $b$ and $z$ with $c$ to find the lexicographically smallest string.

From string $A$ and $B$,

$a$ is equivalent to $x$

$b$ is equivalent to $y$

$c$ is equivalent to $z$

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...