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 double eps = 1e-9;
const int inf = 2000000000;
const long long infLL = 9000000000000000000;
template <typename first, typename second>
ostream &operator<<(ostream &os, const pair<first, second> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ",";
    os << *it;
  }
  return os << "]";
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}
template <typename first, typename second>
ostream &operator<<(ostream &os, const map<first, second> &v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << it->first << " = " << it->second;
  }
  return os << "]";
}
void faltu() { cerr << '\n'; }
template <typename T>
void faltu(T a[], int n) {
  for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
  cerr << '\n';
}
template <typename T, typename... hello>
void faltu(T arg, const hello &...rest) {
  cerr << arg << ' ';
  faltu(rest...);
}
struct FFT {
  struct node {
    double x, y;
    node() {}
    node(double a, double b) : x(a), y(b) {}
    node operator+(const node &a) const {
      return node(this->x + a.x, this->y + a.y);
    }
    node operator-(const node a) const {
      return node(this->x - a.x, this->y - a.y);
    }
    node operator*(const node a) const {
      return node(this->x * a.x - this->y * a.y, this->x * a.y + a.x * this->y);
    }
  };
  int M;
  vector<node> A, B, w[2];
  vector<int> rev;
  long double pi;
  FFT() { pi = 3.1415926535897932384; }
  void init(int n) {
    M = 1;
    while (M < n) M <<= 1;
    M <<= 1;
    A.resize(M);
    B.resize(M);
    w[0].resize(M);
    w[1].resize(M);
    rev.resize(M);
    for (int i = 0; i < M; i++) {
      int j = i, y = 0;
      for (int x = 1; x < M; x <<= 1, j >>= 1) (y <<= 1) += j & 1;
      rev[i] = y;
    }
    for (int i = 0; i < M; i++) {
      w[0][i] = node(cos(2 * pi * i / M), sin(2 * pi * i / M));
      w[1][i] = node(cos(2 * pi * i / M), -sin(2 * pi * i / M));
    }
  }
  void ftransform(vector<node> &A, int p) {
    for (int i = 0; i < M; i++)
      if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int i = 1; i < M; i <<= 1)
      for (int j = 0, t = M / (i << 1); j < M; j += i << 1)
        for (int k = 0, l = 0; k < i; k++, l += t) {
          node x = w[p][l] * A[i + j + k];
          node y = A[j + k];
          A[j + k] = y + x;
          A[j + k + i] = y - x;
        }
    if (p)
      for (int i = 0; i < M; i++) A[i].x /= M;
  }
  void multiply(vector<long long> &P, vector<long long> &Q,
                vector<long long> &res) {
    init(max(P.size(), Q.size()));
    for (int i = 0; i < M; i++) A[i].x = A[i].y = B[i].x = B[i].y = 0;
    for (int i = 0; i < P.size(); i++) A[i].x = P[i];
    for (int i = 0; i < Q.size(); i++) B[i].x = Q[i];
    ftransform(A, 0);
    ftransform(B, 0);
    for (int k = 0; k < M; k++) A[k] = A[k] * B[k];
    ftransform(A, 1);
    res.resize(M);
    for (int i = 0; i < M; i++) res[i] = round(A[i].x);
  }
} fft;
const int mx = 2e5 + 5;
int p[26];
string s, t;
long long pre1[mx], pre2[mx];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  for (int i = 0; i < 26; ++i) cin >> p[i], --p[i];
  cin >> s >> t;
  int s_sz = s.size(), t_sz = t.size();
  for (int i = 0; i < s_sz; ++i) {
    pre1[i] = (s[i] - 'a') * (s[i] - 'a') * p[s[i] - 'a'] * p[s[i] - 'a'];
    if (i) pre1[i] += pre1[i - 1];
  }
  for (int i = 0; i < t_sz; ++i) {
    pre2[i] = (t[i] - 'a') * (t[i] - 'a') * (t[i] - 'a') * (t[i] - 'a');
    if (i) pre2[i] += pre2[i - 1];
  }
  vector<long long> ans(t_sz + s_sz - 1);
  vector<long long> a, b;
  a.resize(t_sz), b.resize(s_sz);
  for (int i = 0; i < t_sz; ++i) {
    a[i] = (t[i] - 'a') * (t[i] - 'a');
  }
  for (int i = 0; i < s_sz; ++i) {
    b[i] = (s[i] - 'a') * (s[i] - 'a') + (p[s[i] - 'a']) * (p[s[i] - 'a']) +
           4 * (s[i] - 'a') * (p[s[i] - 'a']);
  }
  reverse(b.begin(), b.end());
  vector<long long> store;
  fft.multiply(a, b, store);
  for (int i = 0; i < (int)ans.size(); ++i) ans[i] += store[i];
  for (int i = 0; i < t_sz; ++i) {
    a[i] = (t[i] - 'a');
  }
  for (int i = 0; i < s_sz; ++i) {
    b[i] = 2 * p[s[i] - 'a'] * (s[i] - 'a') * (s[i] - 'a') +
           2 * p[s[i] - 'a'] * p[s[i] - 'a'] * (s[i] - 'a');
  }
  reverse(b.begin(), b.end());
  fft.multiply(a, b, store);
  for (int i = 0; i < (int)ans.size(); ++i) ans[i] -= store[i];
  for (int i = 0; i < t_sz; ++i) {
    a[i] = (t[i] - 'a') * (t[i] - 'a') * (t[i] - 'a');
  }
  for (int i = 0; i < s_sz; ++i) {
    b[i] = 2 * (s[i] - 'a') + 2 * p[s[i] - 'a'];
  }
  reverse(b.begin(), b.end());
  fft.multiply(a, b, store);
  for (int i = 0; i < (int)ans.size(); ++i) ans[i] -= store[i];
  for (int i = s_sz - 1, j = 0; i < t_sz; ++i, ++j) {
    long long temp = pre1[s_sz - 1] +
                     (pre2[j + s_sz - 1] - ((j > 0) ? pre2[j - 1] : 0)) +
                     ans[i];
    if (temp == 0)
      cout << '1';
    else
      cout << '0';
  }
  cout << '\n';
}
