#include <bits/stdc++.h>
using namespace std;
inline namespace Infinity {
inline namespace IO {
const char CR = '\n';
const char SP = ' ';
inline void write(const int n) { printf("%d", n); }
inline void write(const unsigned n) { printf("%u", n); }
inline void write(const long long n) { cout << n; }
inline void write(const unsigned long long n) { cout << n; }
inline void writef(const double a, const int n = 15) { printf("%.*f", n, a); }
inline void writef(const long double a, const int n = 18) {
  cout << setprecision(n) << fixed << a;
}
inline void write(const char c) { printf("%c", c); }
inline void write(const char s[]) { printf("%s", s); }
inline void write(const string &s) { cout << s; }
inline void write(const pair<int, int> &p) {
  printf("%d %d", p.first, p.second);
}
template <class T>
inline void write(const T a) {
  for (auto i : a) write(i), write(SP);
}
inline void writeln() { write(CR); }
template <typename T>
inline void writeln(const T &a) {
  write(a);
  write(CR);
}
inline void writefln(const double a, int n) {
  printf("%.*f", n, a);
  write(CR);
}
inline void writefln(const long double a, int n = 18) {
  cout << setprecision(n) << fixed << a << endl;
}
inline void writesln(const int *a, const int l, const int r) {
  for (int i = l; i <= r; i++) printf("%d ", a[i]);
  writeln(CR);
}
template <class T>
inline void writelns(const T a) {
  for (__typeof a.begin() i = a.begin(); i != a.end(); i++) writeln(*i);
}
template <typename T, typename... types>
inline void write(const T &a, const types &...args) {
  write(a);
  write(args...);
}
template <typename... types>
inline void writeln(const types &...args) {
  write(args...);
  write(CR);
}
inline void writelnYN(bool b) { writeln(b ? "YES" : "NO"); }
inline void writelnyn(bool b) { writeln(b ? "Yes" : "No"); }
inline int read(int &n) { return scanf("%d", &n); }
inline int read(long long &n) { return cin >> n ? 1 : -1; }
template <typename T, typename... types>
inline int read(T &n, types &...args) {
  read(n);
  return read(args...);
}
inline char getcc() {
  char c;
  do c = getchar();
  while (c == ' ' || c == '\n');
  return c;
}
inline int getint() {
  int n;
  read(n);
  return n;
}
inline long long getll() {
  long long n;
  read(n);
  return n;
}
inline double getdouble() {
  double n;
  scanf("%lf", &n);
  return n;
}
inline vector<int> getints(int n) {
  vector<int> v(n);
  for (int i = 0; i < n; i++) v[i] = getint();
  return v;
}
inline vector<pair<int, int>> getpairs(int n) {
  vector<pair<int, int>> v(n);
  for (int i = 0; i < n; i++) {
    int a = getint(), b = getint();
    v[i] = pair<int, int>(a, b);
  }
  return v;
}
inline void read(string &str, const unsigned size) {
  char s[size];
  scanf("%s", s);
  str = string(s);
}
inline string getstr(const unsigned size = 1048576) {
  string s;
  read(s, size + 1);
  return s;
}
inline string getln(const unsigned size = 1048576) {
  char s[size + 1];
  scanf("%[^n]", s);
  return string(s);
}
}  // namespace IO
inline namespace Functions {
inline constexpr int ctoi(const char c) { return c - '0'; }
inline constexpr char itoc(const int n) { return n + '0'; }
inline int dtoi(const double d) { return round(d); }
template <typename T>
inline bool in(T x, T l, T r) {
  return l <= x && x <= r;
}
template <class T>
inline int size(const T &a) {
  return a.size();
}
template <typename T1, typename T2>
inline pair<T1, T2> mp(const T1 &a, const T2 &b) {
  return make_pair(a, b);
}
template <class T>
inline void sort(T &a) {
  std::sort(a.begin(), a.end());
}
template <class T1, class T2>
inline void sort(T1 &a, T2 comp) {
  std::sort(a.begin(), a.end(), comp);
}
template <class T1, typename T2>
inline int lbound(const T1 &a, const T2 k) {
  return lower_bound(a.begin(), a.end(), k) - a.begin();
}
template <class T1, typename T2>
inline int ubound(const T1 &a, const T2 k) {
  return upper_bound(a.begin(), a.end(), k) - a.begin();
}
template <class T1, class T2>
int count(T1 &a, T2 k) {
  return ubound(a, k) - lbound(a, k);
}
template <class T1, class T2>
int find(T1 &a, T2 k) {
  return count(a, k) ? lbound(a, k) : -1;
}
template <typename T>
inline void clear(T &a) {
  memset(a, 0, sizeof a);
}
template <typename T>
T gcd(T a, T b) {
  while (b) {
    T t = a % b;
    a = b;
    b = t;
  }
  return a;
}
template <typename T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
long long qpow(long long a, long long b, long long c) {
  return b ? qpow(a * a % c, b >> 1, c) * (b & 1 ? a : 1) % c : 1;
}
template <typename T>
T exGcd(T a, T b, T &x, T &y) {
  T d = a;
  if (b) {
    d = exGcd(b, a % b, y, x);
    y -= a / b * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
template <typename T>
T mps(T l, T r, T k) {
  return ((r - (r % k + k) % k) - (l + (k - l % k) % k)) / k + 1;
}
template <typename T>
T sgn(T a) {
  return a == 0 ? 0 : a > 0 ? 1 : -1;
}
template <typename T>
constexpr T sq(T a) {
  return a * a;
}
}  // namespace Functions
inline namespace TypeDefine {}
}  // namespace Infinity
class Trie {
  class TrieNode {
   public:
    TrieNode() : next(26), data() {}
    vector<TrieNode *> next;
    string data;
  };
  static int atoi(char c) { return c - 'a'; }

 public:
  Trie() : root(new TrieNode) {}
  void insert(const string &str) {
    TrieNode *node = root;
    string t = str;
    reverse(t.begin(), t.end());
    for (int i = 0; t[i]; i++) {
      int c = atoi(tolower(t[i]));
      if (node->next[c] == nullptr) node->next[c] = new TrieNode;
      node = node->next[c];
    }
    node->data = str;
  }
  void solve(string s) {
    bool find = false;
    vector<string> ans;
    function<void(const char *)> dfs = [&](const char *s) {
      if (*s == '\0') find = true;
      if (find) return;
      TrieNode *node = root;
      for (int i = 0; s[i]; i++) {
        if (node->next[atoi(s[i])] == nullptr) return;
        node = node->next[atoi(s[i])];
        if (node->data.empty() == false) {
          ans.push_back(node->data);
          dfs(s + node->data.length());
          if (find) return;
          ans.pop_back();
        }
      }
    };
    dfs(s.data());
    for (string s : ans) write(s, ' ');
  }

 protected:
  TrieNode *root;
};
int main(int, char *[]) {
  getint();
  string s = getstr();
  int m = getint();
  Trie trie;
  for (int i = 0; i < m; i++) trie.insert(getstr());
  trie.solve(s);
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

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. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
inline namespace Infinity {
inline namespace IO {
const char CR = '\n';
const char SP = ' ';
inline void write(const int n) { printf("%d", n); }
inline void write(const unsigned n) { printf("%u", n); }
inline void write(const long long n) { cout << n; }
inline void write(const unsigned long long n) { cout << n; }
inline void writef(const double a, const int n = 15) { printf("%.*f", n, a); }
inline void writef(const long double a, const int n = 18) {
  cout << setprecision(n) << fixed << a;
}
inline void write(const char c) { printf("%c", c); }
inline void write(const char s[]) { printf("%s", s); }
inline void write(const string &s) { cout << s; }
inline void write(const pair<int, int> &p) {
  printf("%d %d", p.first, p.second);
}
template <class T>
inline void write(const T a) {
  for (auto i : a) write(i), write(SP);
}
inline void writeln() { write(CR); }
template <typename T>
inline void writeln(const T &a) {
  write(a);
  write(CR);
}
inline void writefln(const double a, int n) {
  printf("%.*f", n, a);
  write(CR);
}
inline void writefln(const long double a, int n = 18) {
  cout << setprecision(n) << fixed << a << endl;
}
inline void writesln(const int *a, const int l, const int r) {
  for (int i = l; i <= r; i++) printf("%d ", a[i]);
  writeln(CR);
}
template <class T>
inline void writelns(const T a) {
  for (__typeof a.begin() i = a.begin(); i != a.end(); i++) writeln(*i);
}
template <typename T, typename... types>
inline void write(const T &a, const types &...args) {
  write(a);
  write(args...);
}
template <typename... types>
inline void writeln(const types &...args) {
  write(args...);
  write(CR);
}
inline void writelnYN(bool b) { writeln(b ? "YES" : "NO"); }
inline void writelnyn(bool b) { writeln(b ? "Yes" : "No"); }
inline int read(int &n) { return scanf("%d", &n); }
inline int read(long long &n) { return cin >> n ? 1 : -1; }
template <typename T, typename... types>
inline int read(T &n, types &...args) {
  read(n);
  return read(args...);
}
inline char getcc() {
  char c;
  do c = getchar();
  while (c == ' ' || c == '\n');
  return c;
}
inline int getint() {
  int n;
  read(n);
  return n;
}
inline long long getll() {
  long long n;
  read(n);
  return n;
}
inline double getdouble() {
  double n;
  scanf("%lf", &n);
  return n;
}
inline vector<int> getints(int n) {
  vector<int> v(n);
  for (int i = 0; i < n; i++) v[i] = getint();
  return v;
}
inline vector<pair<int, int>> getpairs(int n) {
  vector<pair<int, int>> v(n);
  for (int i = 0; i < n; i++) {
    int a = getint(), b = getint();
    v[i] = pair<int, int>(a, b);
  }
  return v;
}
inline void read(string &str, const unsigned size) {
  char s[size];
  scanf("%s", s);
  str = string(s);
}
inline string getstr(const unsigned size = 1048576) {
  string s;
  read(s, size + 1);
  return s;
}
inline string getln(const unsigned size = 1048576) {
  char s[size + 1];
  scanf("%[^n]", s);
  return string(s);
}
}  // namespace IO
inline namespace Functions {
inline constexpr int ctoi(const char c) { return c - '0'; }
inline constexpr char itoc(const int n) { return n + '0'; }
inline int dtoi(const double d) { return round(d); }
template <typename T>
inline bool in(T x, T l, T r) {
  return l <= x && x <= r;
}
template <class T>
inline int size(const T &a) {
  return a.size();
}
template <typename T1, typename T2>
inline pair<T1, T2> mp(const T1 &a, const T2 &b) {
  return make_pair(a, b);
}
template <class T>
inline void sort(T &a) {
  std::sort(a.begin(), a.end());
}
template <class T1, class T2>
inline void sort(T1 &a, T2 comp) {
  std::sort(a.begin(), a.end(), comp);
}
template <class T1, typename T2>
inline int lbound(const T1 &a, const T2 k) {
  return lower_bound(a.begin(), a.end(), k) - a.begin();
}
template <class T1, typename T2>
inline int ubound(const T1 &a, const T2 k) {
  return upper_bound(a.begin(), a.end(), k) - a.begin();
}
template <class T1, class T2>
int count(T1 &a, T2 k) {
  return ubound(a, k) - lbound(a, k);
}
template <class T1, class T2>
int find(T1 &a, T2 k) {
  return count(a, k) ? lbound(a, k) : -1;
}
template <typename T>
inline void clear(T &a) {
  memset(a, 0, sizeof a);
}
template <typename T>
T gcd(T a, T b) {
  while (b) {
    T t = a % b;
    a = b;
    b = t;
  }
  return a;
}
template <typename T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
long long qpow(long long a, long long b, long long c) {
  return b ? qpow(a * a % c, b >> 1, c) * (b & 1 ? a : 1) % c : 1;
}
template <typename T>
T exGcd(T a, T b, T &x, T &y) {
  T d = a;
  if (b) {
    d = exGcd(b, a % b, y, x);
    y -= a / b * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
template <typename T>
T mps(T l, T r, T k) {
  return ((r - (r % k + k) % k) - (l + (k - l % k) % k)) / k + 1;
}
template <typename T>
T sgn(T a) {
  return a == 0 ? 0 : a > 0 ? 1 : -1;
}
template <typename T>
constexpr T sq(T a) {
  return a * a;
}
}  // namespace Functions
inline namespace TypeDefine {}
}  // namespace Infinity
class Trie {
  class TrieNode {
   public:
    TrieNode() : next(26), data() {}
    vector<TrieNode *> next;
    string data;
  };
  static int atoi(char c) { return c - 'a'; }

 public:
  Trie() : root(new TrieNode) {}
  void insert(const string &str) {
    TrieNode *node = root;
    string t = str;
    reverse(t.begin(), t.end());
    for (int i = 0; t[i]; i++) {
      int c = atoi(tolower(t[i]));
      if (node->next[c] == nullptr) node->next[c] = new TrieNode;
      node = node->next[c];
    }
    node->data = str;
  }
  void solve(string s) {
    bool find = false;
    vector<string> ans;
    function<void(const char *)> dfs = [&](const char *s) {
      if (*s == '\0') find = true;
      if (find) return;
      TrieNode *node = root;
      for (int i = 0; s[i]; i++) {
        if (node->next[atoi(s[i])] == nullptr) return;
        node = node->next[atoi(s[i])];
        if (node->data.empty() == false) {
          ans.push_back(node->data);
          dfs(s + node->data.length());
          if (find) return;
          ans.pop_back();
        }
      }
    };
    dfs(s.data());
    for (string s : ans) write(s, ' ');
  }

 protected:
  TrieNode *root;
};
int main(int, char *[]) {
  getint();
  string s = getstr();
  int m = getint();
  Trie trie;
  for (int i = 0; i < m; i++) trie.insert(getstr());
  trie.solve(s);
  return 0;
}

```