Question
Str_ing
You are given N strings S1, S2,. ., SN as well as M strings T1, T2,. ., TM.
You have to create a string Y such that Y is a concatenation of a permutation of all N strings S1, S2,. ., SN separated by underscore (_). Length of Y should be between 3 and 16 inclusive and also Y should be constructed in such a way that it doesn’t match any of the M strings T1, T2,. ., TM.
If multiple answers are possible, output any string Y. If no such Y is possible, output -1
You have to create a string Y such that Y is a concatenation of a permutation of all N strings S1, S2,. ., SN separated by underscore (_). Length of Y should be between 3 and 16 inclusive and also Y should be constructed in such a way that it doesn’t match any of the M strings T1, T2,. ., TM.
If multiple answers are possible, output any string Y. If no such Y is possible, output -1
Input
The first line of the input contains a two integers N and M
The second line contains N strings S1, S2,. ., SN
The third line contains M strings T1, T2,. ., TM
Constraints:
1) 1 <= N <= 8
2) 0 <= M <= 10^5
3) N and M are integers.
4) 1 <= ∣Si∣ <= 16
5) N - 1 + ∑|Si| <= 16
6) Si != Sj if i != j.
7) Si is a string consisting of lowercase English letters.
8) 3 <= |Ti| <= 16
9) Ti != Tj if i != j.
10) Ti is a string consisting of lowercase English letters and _.
The second line contains N strings S1, S2,. ., SN
The third line contains M strings T1, T2,. ., TM
Constraints:
1) 1 <= N <= 8
2) 0 <= M <= 10^5
3) N and M are integers.
4) 1 <= ∣Si∣ <= 16
5) N - 1 + ∑|Si| <= 16
6) Si != Sj if i != j.
7) Si is a string consisting of lowercase English letters.
8) 3 <= |Ti| <= 16
9) Ti != Tj if i != j.
10) Ti is a string consisting of lowercase English letters and _.
Output
Output the answer string Y in a single line
Example
Sample Input 1:
2 2
newton school
newwton school_newton
Sample Output 1:
newton_school
Explanation 1:
Strings like newton_school and school_newton are possible but only newton_school can be considered because school_newton is already in the second list.
Sample Input 2:
2 2
newton school
school_newton newton_school
Sample Output 2:
-1
Sample Input 3:
4 4
ab cd ef gh
adsf fueh ____ ab_cd_ef_gh_
Sample Output 3:
ab_cd_ef_gh
2 2
newton school
newwton school_newton
Sample Output 1:
newton_school
Explanation 1:
Strings like newton_school and school_newton are possible but only newton_school can be considered because school_newton is already in the second list.
Sample Input 2:
2 2
newton school
school_newton newton_school
Sample Output 2:
-1
Sample Input 3:
4 4
ab cd ef gh
adsf fueh ____ ab_cd_ef_gh_
Sample Output 3:
ab_cd_ef_gh