You are given a permutation p consisting of exactly 26 integers from 1 to 26 (since it is a permutation, each integer from 1 to 26 occurs in p exactly once) and two strings s and t consisting of lowercase Latin letters.

A substring t' of string t is an occurence of string s if the following conditions are met:

  1. |t'| = |s|; 
  2. for each i ∈ [1, |s|], either s_i = t'_i, or p_{idx(s_i)} = idx(t'_i), where idx(c) is the index of character c in Latin alphabet (idx(a) = 1, idx(b) = 2, idx(z) = 26). 



For example, if p_1 = 2, p_2 = 3, p_3 = 1, s = abc, t = abcaaba, then three substrings of t are occurences of s (they are t' = abc, t' = bca and t' = aba).

For each substring of t having length equal to |s|, check if it is an occurence of s.

Input

The first line contains 26 integers p_1, p_2, ..., p_{26} (1 ≤ p_i ≤ 26, all these integers are pairwise distinct).

The second line contains one string s, and the third line contains one string t (2 ≤ |s| ≤ |t| ≤ 2 ⋅ 10^5) both consisting of lowercase Latin letters.

Output

Print a string of |t| - |s| + 1 characters, each character should be either 0 or 1. The i-th character should be 1 if and only if the substring of t starting with the i-th character and ending with the (i + |s| - 1)-th character (inclusive) is an occurence of s.

Example

Input


2 3 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
abc
abcaaba


Output


11001
#include <bits/stdc++.h>
using namespace std;
const int P = 1004535809;
inline int mpow(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = (long long)a * a % P)
    if (b & 1) ans = (long long)ans * a % P;
  return ans;
}
const int gn = 3, ign = mpow(gn, P - 2);
const int N = 1e6 + 10;
int roots[N][2];
bool initialized = 0;
void root_init() {
  initialized = 1;
  for (int len = 1; len < N; len <<= 1) {
    roots[len][0] = mpow(ign, (P - 1) / len);
    roots[len][1] = mpow(gn, (P - 1) / len);
  }
}
vector<int> rev;
void fft(vector<int> &a, int flg) {
  if (!initialized) root_init();
  int n = a.size();
  if (rev.size() != n) {
    rev.resize(n);
    for (int i = 0; i < n; ++i)
      rev[i] = rev[i >> 1] >> 1 | ((i & 1) ? n >> 1 : 0);
  }
  for (int i = 0; i < n; ++i)
    if (rev[i] < i) swap(a[i], a[rev[i]]);
  for (int len = 2; len <= n; len <<= 1) {
    int k = len >> 1, wn = roots[len][flg == 1];
    for (int i = 0; i < n; i += len) {
      for (int j = i, w = 1; j < i + k; ++j, w = (long long)w * wn % P) {
        int tmp = (long long)a[j + k] * w % P;
        int x = a[j] + tmp, y = a[j] - tmp;
        a[j] = x >= P ? x - P : x;
        a[j + k] = y < 0 ? y + P : y;
      }
    }
  }
  if (flg == -1) {
    int inv = mpow(n, P - 2);
    for (int i = 0; i < n; ++i) a[i] = (long long)a[i] * inv % P;
  }
}
struct Poly {
  vector<int> a;
  Poly() {}
  Poly(int v) {
    v %= P;
    if (v < 0) v += P;
    a = {v};
  }
  Poly(const vector<int> &v) { a = v; }
  Poly(const initializer_list<int> &l) { a = l; }
  int size() const { return a.size(); }
  int deg() const { return size() - 1; }
  int operator[](int k) const {
    if (k < 0 || k >= size())
      return 0;
    else
      return a[k];
  }
  int &operator[](int k) {
    assert(0 <= k && k < size());
    return a[k];
  }
  Poly modxk(int k) const {
    if (a.size() <= k)
      return Poly(a);
    else
      return Poly(vector<int>(a.begin(), a.begin() + k));
  }
  Poly reverse() const {
    vector<int> res = a;
    ::reverse(res.begin(), res.end());
    return Poly(res);
  }
  friend Poly operator+(const Poly a, const Poly &b) {
    int n = max(a.size(), b.size());
    Poly ans = vector<int>(n);
    for (int i = 0; i < n; ++i) {
      ans[i] = a[i] + b[i];
      if (ans[i] >= P) ans[i] -= P;
    }
    return ans;
  }
  friend Poly operator-(const Poly a, const Poly &b) {
    int n = max(a.size(), b.size());
    Poly ans = vector<int>(n);
    for (int i = 0; i < n; ++i) {
      ans[i] = a[i] - b[i];
      if (ans[i] < 0) ans[i] += P;
    }
    return ans;
  }
  friend Poly operator*(const Poly a, const Poly &b) {
    int n = a.deg(), m = b.deg();
    int lim = 1;
    while (lim <= n + m) lim <<= 1;
    vector<int> f = a.a, g = b.a;
    f.resize(lim), g.resize(lim);
    fft(f, 1), fft(g, 1);
    for (int i = 0; i < lim; ++i) f[i] = (long long)f[i] * g[i] % P;
    fft(f, -1);
    Poly ans = vector<int>(n + m + 1);
    for (int i = 0; i <= n + m; ++i) ans[i] = f[i];
    return ans;
  }
  Poly &operator+=(const Poly &o) { return (*this) = (*this) + o; }
  Poly &operator-=(const Poly &o) { return (*this) = (*this) - o; }
  Poly &operator*=(const Poly &o) { return (*this) = (*this) * o; }
  Poly inv(int m) const {
    int k = 1;
    Poly x(mpow(a[0], P - 2));
    while (k < m) {
      k <<= 1;
      x = (x * (2 - modxk(k) * x)).modxk(k);
    }
    return x.modxk(m);
  }
  Poly sqrt(int m) const {
    Poly x(1);
    int k = 1;
    while (k < m) {
      k <<= 1;
      x = ((2 * x.modxk(k)).inv(k) * ((x * x).modxk(k) + modxk(k))).modxk(k);
    }
    return x.modxk(m);
  }
  Poly deriv() const {
    Poly ans = *this;
    for (int i = 0; i < ans.size() - 1; ++i)
      ans[i] = (long long)a[i + 1] * (i + 1) % P;
    ans[size() - 1] = 0;
    return ans;
  }
  Poly integ() const {
    Poly ans = *this;
    for (int i = 1; i < ans.size(); ++i)
      ans[i] = (long long)a[i - 1] * mpow(i, P - 2) % P;
    ans[0] = 0;
    return ans;
  }
  Poly ln(int m) const { return (deriv() * inv(m)).integ().modxk(m); }
  Poly exp(int m) const {
    Poly x(1);
    int k = 1;
    while (k < m) {
      k <<= 1;
      x = (x * (1 - x.ln(k) + modxk(k))).modxk(k);
    }
    return x.modxk(m);
  }
  friend pair<Poly, Poly> divmod(const Poly &a, const Poly &b) {
    int n = a.deg(), m = b.deg();
    if (n < m) {
      return make_pair(Poly(), a);
    }
    Poly ar = a.reverse(), br = b.reverse();
    Poly q = (ar * br.inv(n - m + 1)).modxk(n - m + 1);
    q = q.reverse();
    return make_pair(q, (a - b * q).modxk(m));
  }
  friend Poly operator/(const Poly &a, const Poly &b) {
    return divmod(a, b).first;
  }
  friend Poly operator%(const Poly &a, const Poly &b) {
    return divmod(a, b).second;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  vector<int> val(26);
  mt19937 rng(220037);
  for (int i = 0; i < 26; ++i) val[i] = rng() % P;
  vector<int> p(26);
  for (int i = 0; i < (int)p.size(); ++i) {
    int c;
    cin >> c;
    p[c - 1] = i;
  }
  string t, s;
  cin >> t >> s;
  int m = (int)t.size(), n = (int)s.size();
  vector<Poly> T(5, vector<int>(m));
  vector<Poly> S(5, vector<int>(n));
  for (int i = 0; i < m; ++i) {
    int c = val[t[i] - 'a'];
    T[0][i] = 1;
    T[1][i] = c;
    T[2][i] = (long long)c * c % P;
    T[3][i] = (long long)T[2][i] * c % P;
    T[4][i] = (long long)T[3][i] * c % P;
  }
  for (int i = 0; i < n; ++i) {
    int u = val[s[i] - 'a'], v = val[p[s[i] - 'a']];
    S[0][i] = ((long long)u * u % P * v % P * v % P) % P;
    S[1][i] = ((long long)(P - 2) * u % P * u % P * v % P +
               (long long)(P - 2) * u % P * v % P * v % P) %
              P;
    S[2][i] = ((long long)u * u % P + (long long)4 * u % P * v % P +
               (long long)v * v % P) %
              P;
    S[3][i] = ((long long)(P - 2) * u % P + (long long)(P - 2) * v % P) % P;
    S[4][i] = 1;
  }
  for (int i = 0; i < 5; ++i) {
    T[i] = T[i].reverse();
  }
  Poly Ans;
  for (int i = 0; i < 5; ++i) Ans += S[i] * T[i];
  for (int i = 0; i + m - 1 < n; ++i) {
    if (Ans[m + i - 1] == 0)
      cout << "1";
    else
      cout << "0";
  }
  cout << '\n';
  return 0;
}
