633_C. Spy Syndrome 2_10312
After observing the results of Spy Syndrome, Yash realised the errors of his ways. He now believes that a super spy such as Siddhant can't use a cipher as basic and ancient as Caesar cipher. After many weeks of observation of Siddhant’s sentences, Yash determined a new cipher technique.

For a given sentence, the cipher is processed as: 

  1. Convert all letters of the sentence to lowercase. 
  2. Reverse each of the words of the sentence individually. 
  3. Remove all the spaces in the sentence. 



For example, when this cipher is applied to the sentence

Kira is childish and he hates losing

the resulting string is

ariksihsidlihcdnaehsetahgnisol

Now Yash is given some ciphered string and a list of words. Help him to find out any original sentence composed using only words from the list. Note, that any of the given words could be used in the sentence multiple times.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 10 000) — the length of the ciphered text. The second line consists of n lowercase English letters — the ciphered text t.

The third line contains a single integer m (1 ≤ m ≤ 100 000) — the number of words which will be considered while deciphering the text. Each of the next m lines contains a non-empty word wi (|wi| ≤ 1 000) consisting of uppercase and lowercase English letters only. It's guaranteed that the total length of all words doesn't exceed 1 000 000.

Output

Print one line — the original sentence. It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any of those.

Examples

Input

30
ariksihsidlihcdnaehsetahgnisol
10
Kira
hates
is
he
losing
death
childish
L
and
Note


Output

Kira is childish and he hates losing 


Input

12
iherehtolleh
5
HI
Ho
there
HeLLo
hello


Output

HI there HeLLo 

Note

In sample case 2 there may be multiple accepted outputs, "HI there HeLLo" and "HI there hello" you may output any of them. 
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100010;
int lower(int character) {
  if ('a' <= character && character <= 'z') return character;
  return character - 'A' + 'a';
}
struct Trie {
  Trie *link[26];
  int ind;
  Trie(int ind) : ind(ind) {
    for (int i = 0; i < 26; ++i) link[i] = NULL;
  }
} * root;
string S, a[MAX];
int dp[MAX], pre[MAX], ans[MAX], N, M;
void add(string a, int ind) {
  int len = a.size();
  reverse(a.begin(), a.end());
  Trie *q, *p = root;
  for (int i = 0, j; i < len; ++i) {
    j = lower(a[i]) - 'a';
    q = p->link[j];
    if (q == NULL) p->link[j] = q = new Trie(-1);
    p = q;
  }
  p->ind = ind;
}
void openFile() { freopen("in.inp", "r", stdin); }
int main() {
  ios::sync_with_stdio(false);
  cin >> N;
  cin >> S;
  cin >> M;
  root = new Trie(-1);
  for (int i = 0; i < M; ++i) {
    cin >> a[i];
    add(a[i], i);
  }
  reverse(S.begin(), S.end());
  S = "#" + S;
  dp[0] = 1;
  Trie *p;
  for (int i = 1, j; i <= N; ++i) {
    p = root;
    j = i;
    dp[i] = 0;
    while (j >= 1 && dp[i] == 0) {
      p = p->link[S[j] - 'a'];
      if (p == NULL) break;
      if (p->ind != -1 && dp[j - 1]) {
        dp[i] = 1;
        pre[i] = j - 1;
        ans[i] = p->ind;
        break;
      }
      --j;
    }
  }
  int i = N;
  while (i > 0) {
    cout << a[ans[i]];
    i = pre[i];
    if (i) cout << " ";
  }
  return 0;
}

12
iherehtolleh
5
HI
Ho
there
HeLLo
hello
 30
ariksihsidlihcdnaehsetahgnisol
10
Kira
hates
is
he
losing
death
childish
L
and
Note
 5
cbaed
6
bc
ea
ab
cd
abc
de
 11
aaaaaaaaaaa
3
aaaa
aaaaa
aaaaaa
 3
aab
2
aa
baa
 3
aab
2
a
baa
 7
kirkirk
2
rik
krik
 9
aaaaaaaaa
2
aa
aaa
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 7
abababc
2
ba
cba
 5
lehet
3
el
hel
te
 11
aaaaaaaaaaa
3
abaa
aaaaa
aaaaaa
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
a
aa
aaa
aaaa
aaaaa
aabaaa
aaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 12
iherehtolleh
5
HI
Hp
there
HeLLo
hello
 12
iherehtolleh
5
HI
Hp
there
HeLLo
helko
 3
aaa
2
a
baa
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
b
aa
aaa
aaaa
aaaaa
aabaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 30
ariksihsidlihcdnaehsetahgnisol
10
Kira
hates
is
he
losing
death
childish
L
and
Oote
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
a
ba
aaa
aaab
aaaaa
aaaaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 5
cbaed
6
bc
eb
ab
cd
abc
de
 7
kirkrik
2
rik
kirk
 71
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
8
a
ba
aaa
aaaa
aaaaa
aaaaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
a
aa
aaa
aaaa
aaaaa
aaabaa
aaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 12
iherehtolleh
5
HI
Ho
there
HeLLo
helko
 11
aaaaaaaaaaa
3
aaba
aaaaa
aaaaaa
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
a
aa
aaa
aaaa
aaaaa
aabaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 12
iherehtolleh
5
HI
pH
there
HeLLo
helko
 3
aaa
1
a
baa
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 11
aaaaaaaaaaa
3
aaab
aaaaa
aaaaaa
 12
iherehtolleh
5
HI
pH
there
HeLLo
hekko
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
a
ba
aaa
aaaa
aaaaa
aaaaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 12
iherehtolleh
5
HI
pH
there
HeLLo
hfkko
 12
iherehtolleh
5
HI
Hp
there
HeLLo
heljo
 12
iherehtolleh
5
HI
Go
there
HeLLo
helko
 12
iherehtolleh
5
HI
oH
there
HeLLo
helko
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
a
aa
aaa
aaaa
aaaaa
aaaaaa
baaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
b
aa
aaa
aaaa
aaaba
aabaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 12
iherehtolleh
5
HI
pH
there
HeLLo
okkeh
 12
iherehtolleh
5
HI
oG
there
HeLLo
helko
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
b
aa
aaa
aaba
aaaba
aabaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 12
iherehtolleh
5
HI
pH
there
HeLLo
okleh
 12
iherehtolleh
5
HI
nG
there
HeLLo
helko
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
b
aa
aaa
aaba
aaaba
aabaaa
aabaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
b
aa
aaa
aaba
aaaba
aabaaa
babaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 30
ariksihsidlihcdnaehsetahgnisol
10
Kira
hates
is
he
losing
htaed
childish
L
and
Note
 11
aaaaaaaaaaa
3
baaa
aaaaa
aaaaaa
 12
iherehtolleh
5
HI
pH
there
HeLLo
hello
 12
iherehtolleh
5
HI
nH
there
HeLLo
helko
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
a
aa
aaa
aaaa
aaaaa
abbaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 12
iherehtolleh
5
HI
pH
there
HeLLo
iekko
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
b
aa
aaa
abaa
aaaaa
aabaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 12
iherehtolleh
5
HI
pH
there
HeLLo
ofkkh
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
b
aa
aaa
aaaa
aaaaa
aaaaaa
baaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
b
aa
aaa
aaaa
aaabb
aabaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 12
iherehtolleh
5
HI
pH
there
HeLLo
kkoeh
 71
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
b
aa
aaa
baaa
aaaba
aabaaa
aaaabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 12
iherehtolleh
5
HI
Hp
there
HeLLo
okleh

HI there hello
 Kira is childish and he hates losing
 abc de
 aaaaa aaaaaa 
 baa
 baa
 rik krik
 aaa aa aa aa  aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
 ba ba cba
 hel te
 aaaaaa aaaaa   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab   HI there hello   HI there HeLLo   a a a   b aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa   Kira is childish and he hates losing   aaab a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a   abc de   rik kirk   a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ba   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab   HI there HeLLo   aaaaaa aaaaa   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab   HI there HeLLo   a a a   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab   aaaaaa aaaaa   HI there HeLLo   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab   HI there HeLLo   HI there HeLLo   HI there HeLLo   HI there HeLLo   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab   b aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa   HI there HeLLo   HI there HeLLo   b aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa   HI there HeLLo   HI there HeLLo   b aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa   b aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa   Kira is childish and he hates losing   aaaaaa aaaaa   HI there hello   HI there HeLLo   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab   HI there HeLLo   b aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa   HI there HeLLo   b aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa   b aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa   HI there HeLLo   b aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa aa   HI there HeLLo  