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 MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = acos((long double)-1);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
int pct(int x) { return __builtin_popcount(x); }
int bit(int x) { return 31 - __builtin_clz(x); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
template <class A>
void re(complex<A>& c);
template <class A, class B>
void re(pair<A, B>& p);
template <class A>
void re(vector<A>& v);
template <class A, size_t SZ>
void re(array<A, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& d) {
  string t;
  re(t);
  d = stod(t);
}
void re(long double& d) {
  string t;
  re(t);
  d = stold(t);
}
template <class H, class... T>
void re(H& h, T&... t) {
  re(h);
  re(t...);
}
template <class A>
void re(complex<A>& c) {
  A a, b;
  re(a, b);
  c = {a, b};
}
template <class A, class B>
void re(pair<A, B>& p) {
  re(p.first, p.second);
}
template <class A>
void re(vector<A>& x) {
  for (auto& a : x) re(a);
}
template <class A, size_t SZ>
void re(array<A, SZ>& x) {
  for (auto& a : x) re(a);
}
template <class A, class B>
string to_string(pair<A, B> p);
template <class A>
string to_string(complex<A> c) {
  return to_string(make_pair(c.real(), c.imag()));
}
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(char c) {
  string second = "";
  second += c;
  return second;
}
string to_string(string second) { return second; }
string to_string(const char* second) { return (string)second; }
string to_string(vector<bool> v) {
  bool fst = 1;
  string res = "{";
  for (int i = (0); i < ((int)v.size()); ++i) {
    if (!fst) res += ", ";
    fst = 0;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t SZ>
string to_string(bitset<SZ> b) {
  string res = "";
  for (int i = (0); i < (SZ); ++i) res += char('0' + b[i]);
  return res;
}
template <class T>
string to_string(T v) {
  bool fst = 1;
  string res = "{";
  for (const auto& x : v) {
    if (!fst) res += ", ";
    fst = 0;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class A>
void pr(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void pr(const H& h, const T&... t) {
  pr(h);
  pr(t...);
}
void ps() { pr("\n"); }
template <class H, class... T>
void ps(const H& h, const T&... t) {
  pr(h);
  if (sizeof...(t)) pr(" ");
  ps(t...);
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void unsyncIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
void setIO(string second = "") {
  unsyncIO();
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
struct mi {
  typedef decay<decltype(MOD)>::type T;
  T v;
  explicit operator T() const { return v; }
  mi() { v = 0; }
  mi(long long _v) {
    v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
    if (v < 0) v += MOD;
  }
  friend bool operator==(const mi& a, const mi& b) { return a.v == b.v; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.v < b.v; }
  friend void re(mi& a) {
    long long x;
    re(x);
    a = mi(x);
  }
  friend string to_string(mi a) { return to_string(a.v); }
  mi& operator+=(const mi& m) {
    if ((v += m.v) >= MOD) v -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((v -= m.v) < 0) v += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    v = (long long)v * m.v % MOD;
    return *this;
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
  }
  mi operator-() const { return mi(-v); }
  mi& operator++() { return *this += 1; }
  mi& operator--() { return *this -= 1; }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
vector<vector<mi> > comb;
void genComb(int SZ) {
  comb.assign(SZ, vector<mi>(SZ));
  comb[0][0] = 1;
  for (int i = (1); i < (SZ); ++i)
    for (int j = (0); j < (i + 1); ++j)
      comb[i][j] = comb[i - 1][j] + (j ? comb[i - 1][j - 1] : 0);
}
const int root = 3;
int size(int second) { return second > 1 ? 32 - __builtin_clz(second - 1) : 0; }
void genRoots(vector<complex<double> >& roots) {
  int n = (int)roots.size();
  double ang = 2 * PI / n;
  for (int i = (0); i < (n); ++i)
    roots[i] = complex<double>(cos(ang * i), sin(ang * i));
}
void genRoots(vector<mi>& roots) {
  int n = (int)roots.size();
  mi r = pow(mi(root), (MOD - 1) / n);
  roots[0] = 1;
  for (int i = (1); i < (n); ++i) roots[i] = roots[i - 1] * r;
}
template <class T>
void fft(vector<T>& a, const vector<T>& rts, bool inv = 0) {
  int n = (int)a.size();
  for (int i = 1, j = 0; i < n; i++) {
    int bit = n >> 1;
    for (; j & bit; bit /= 2) j ^= bit;
    j ^= bit;
    if (i < j) swap(a[i], a[j]);
  }
  for (int len = 1; len < n; len *= 2)
    for (int i = 0; i < n; i += 2 * len)
      for (int j = (0); j < (len); ++j) {
        T u = a[i + j], v = a[i + j + len] * rts[n / 2 / len * j];
        a[i + j] = u + v, a[i + j + len] = u - v;
      }
  if (inv) {
    reverse(1 + begin(a), end(a));
    T i = T(1) / T(n);
    for (auto& x : a) x *= i;
  }
}
template <class T>
vector<T> mul(vector<T> a, vector<T> b) {
  if (!min((int)a.size(), (int)b.size())) return {};
  int second = (int)a.size() + (int)b.size() - 1, n = 1 << size(second);
  vector<T> roots(n);
  genRoots(roots);
  a.resize(n), fft(a, roots);
  b.resize(n), fft(b, roots);
  for (int i = (0); i < (n); ++i) a[i] *= b[i];
  fft(a, roots, 1);
  a.resize(second);
  return a;
}
vector<complex<double> > E[5];
vector<complex<double> > T[5];
vector<complex<double> > R[5];
int p[26];
int main() {
  setIO();
  for (int i = 1; i <= 26; i++) {
    cin >> p[i - 1];
    p[i - 1]--;
  }
  string second, t;
  cin >> second >> t;
  int n = (int)t.size();
  int m = (int)second.size();
  for (int i = 0; i < 5; i++) {
    E[i].resize(n);
    T[i].resize(n);
  }
  for (int i = 0; i < m; i++) {
    int S = second[i] - 'a';
    int P = p[second[i] - 'a'];
    int j = m - 1 - i;
    E[0][j] = complex<double>(S * S * P * P, 0);
    E[1][j] = complex<double>(-2 * S * P * P - 2 * S * S * P, 0);
    E[2][j] = complex<double>(P * P + 4 * S * P + S * S, 0);
    E[3][j] = complex<double>(-2 * P - 2 * S);
    E[4][j] = complex<double>(1, 0);
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 5; j++) {
      T[j][i] = complex<double>(pow(t[i] - 'a', j), 0);
    }
  }
  for (int i = 0; i < 5; i++) {
    R[i] = mul(E[i], T[i]);
  }
  for (int i = 0; i < n - m + 1; i++) {
    complex<double> sum = 0;
    for (int j = 0; j < 5; j++) {
      sum += R[j][i + m - 1];
    }
    double a = real(sum);
    if (round(a) == 0) {
      cout << '1';
    } else
      cout << '0';
  }
}
