3594번 - A+B 다국어

The Research Institute of Given Strings (RIGS) is a well-known place where people investigate anything about strings. Peter works in the department of string operations of RIGS. His department invents different ways to add, multiply, divide strings and even to take a logarithm of a string based on another one.

Now Peter is involved in the new project concerning orthogonal strings. Peter proposed that two strings P = P₁P₂...P_n and Q = Q₁Q₂...Q_n of equal length n are called orthogonal, if P_i ≠ Q_i for each i in the range 1..n. String S of length n is called orthogonal to set of strings V = {V₁, V₂, . . . , V_m} (each of length n too) if S is orthogonal to V_j for any j in range 1..m.

Peter’s task is to invent the operation of orthogonal sum of two given strings. The current Peter’s proposal allows to add only strings on a basis of some set, if they are orthogonal to this set. To do this, Peter selects an arbitrary set of strings V such that all strings in V have the same length n. Then Peter takes all strings of length n orthogonal to V over a fixed alphabet and sorts them, thus obtaining a sorted sequence of strings T. Let’s denote the length of sequence T as M, and enumerate the elements of this sequence as T₀, T₁, . . . , T_M−1. Now Peter says that the orthogonal sum of two strings A = T_a and B = T_b is a string C = T_c where c = (a + b) mod M.

Your task is to find the orthogonal sum of two given strings A and B on the basis of a given set V over the alphabet of small English letters.

The first line of the input file contains two integers: n — the length of each string (1 ≤ n ≤ 100 000) and k — the cardinality of V (1 ≤ n · k ≤ 100 000). The next k lines contains strings V₁, V₂, . . . , V_k.

The last two lines contain strings A and B of length n. All strings V_j, A and B consist of small letters of English alphabet. It is guaranteed that A and B are orthogonal to V.

Output the orthogonal sum of strings A and B on the basis V .