In eukaryotes, some parts of genes which are called introns are not utilized in the mRNA expression process. Your friend, Cansu, who is a bioinformatician, seeks assistance in determining the intron sequence of a gene based on the nucleotides of the gene and the mRNA produced from it. You can refer to the table below for complementary nucleotides:

You can be sure that the provided DNA sequence won't contain more than one intron region.

The format of the gene sequence is structured as follows: <exon1> <intron> <exon2>

The lengths of <exon1>, <intron>, and <exon2> parts may be 0. If there are multiple potential intron sequences, you should prioritize maximizing the length of <exon1>.

Input

In the first line of each test case, length of gene sequence is given.

For the second line of each test case, length of mRNA sequence is given.

In the third line of each test case, gene sequence is given.

In the forth line of each test case, mRNA sequence is given.

Length of these sequences will be less than or equal to \(10^6\).

Output

Only print the intron sequence.

Examples

Input 1:

9
6
AATTCGTCA
UUAAGU

Output 1:

GTC

Input 2:

23
18
ATATGCATCCCGTACGTACCGAT
UAUACGUAGGGCUGGCUA

Output 2:

TACGT

Explanation

Input 1: The exon1 sequence which has maximum length among possible ones is AATTC, which makes A exon2 sequence and GTC intron sequence.