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;
struct CD {
  double r, i;
  CD(double r = 0, double i = 0) : r(r), i(i) {}
  double real() const { return r; }
  void operator/=(const int c) { r /= c, i /= c; }
};
CD operator*(const CD& a, const CD& b) {
  return CD(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r);
}
CD operator+(const CD& a, const CD& b) { return CD(a.r + b.r, a.i + b.i); }
CD operator-(const CD& a, const CD& b) { return CD(a.r - b.r, a.i - b.i); }
const double pi = acos(-1.0);
const int MAXN = 1 << 19;
CD cp1[MAXN + 9], cp2[MAXN + 9];
int R[MAXN + 9];
void dft(CD* a, int n, bool inv) {
  for (int i = 0, colchin = n; i < colchin; ++i)
    if (R[i] < i) swap(a[R[i]], a[i]);
  for (int m = 2; m <= n; m *= 2) {
    double z = 2 * pi / m * (inv ? -1 : 1);
    CD wi = CD(cos(z), sin(z));
    for (int j = 0; j < n; j += m) {
      CD w(1);
      for (int k = j, k2 = j + m / 2; k2 < j + m; k++, k2++) {
        CD u = a[k];
        CD v = a[k2] * w;
        a[k] = u + v;
        a[k2] = u - v;
        w = w * wi;
      }
    }
  }
  if (inv)
    for (int i = 0, colchin = n; i < colchin; ++i) a[i] /= n;
}
vector<double> multiply(vector<CD>& p1, vector<CD>& p2) {
  int n = p1.size() + p2.size() + 1;
  int m = 1, cnt = 0;
  while (m <= n) m += m, cnt++;
  for (int i = 0, colchin = m; i < colchin; ++i) {
    R[i] = 0;
    for (int j = 0, colchin = cnt; j < colchin; ++j)
      R[i] = (R[i] << 1) | ((i >> j) & 1);
  }
  for (int i = 0, colchin = m; i < colchin; ++i) cp1[i] = 0, cp2[i] = 0;
  for (int i = 0, colchin = p1.size(); i < colchin; ++i) cp1[i] = p1[i];
  for (int i = 0, colchin = p2.size(); i < colchin; ++i) cp2[i] = p2[i];
  dft(cp1, m, false);
  dft(cp2, m, false);
  for (int i = 0, colchin = m; i < colchin; ++i) cp1[i] = cp1[i] * cp2[i];
  dft(cp1, m, true);
  vector<double> res;
  n -= 2;
  for (int i = 0, colchin = n; i < colchin; ++i) res.push_back(cp1[i].real());
  return res;
}
vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
int perm[30];
int cycleSizes[30];
int cycleNum;
int cycleMember[30];
int cycleMemberCnt[30];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (int i = 0, colchin = 26; i < colchin; ++i) {
    cin >> perm[i];
    perm[i]--;
  }
  memset(cycleMember, -1, sizeof cycleMember);
  for (int i = 0, colchin = 26; i < colchin; ++i) {
    if (cycleMember[i] == -1) {
      cycleNum++;
      int current = i;
      int cnt = 0;
      while (cycleMember[current] == -1) {
        cycleMember[current] = cycleNum - 1;
        cycleMemberCnt[current] = cnt;
        cnt++;
        current = perm[current];
      }
      cycleSizes[cycleNum - 1] = cnt;
    }
  }
  string s, t;
  cin >> s >> t;
  string frstTest = "";
  for (int i = 0, colchin = s.size(); i < colchin; ++i) {
    frstTest += to_string(cycleMember[s[i] - 'a']);
  }
  for (int i = 0, colchin = t.size(); i < colchin; ++i) {
    frstTest += to_string(cycleMember[t[i] - 'a']);
  }
  vector<int> firstTest = z_function(frstTest);
  vector<CD> P(t.size(), CD(0, 0)), Q(s.size(), CD(0, 0));
  for (int i = 0, colchin = t.size(); i < colchin; ++i) {
    double ang = (pi - 2 * pi * cycleMemberCnt[t[i] - 'a']) /
                 (cycleSizes[cycleMember[t[i] - 'a']]);
    P[i] = CD(cos(ang), sin(ang));
  }
  double expected = 0;
  for (int i = 0, colchin = s.size(); i < colchin; ++i) {
    double ang = (2 * pi * cycleMemberCnt[s[i] - 'a']) /
                 (cycleSizes[cycleMember[s[i] - 'a']]);
    Q[s.size() - 1 - i] = CD(cos(ang), sin(ang));
    expected += cos(pi / cycleSizes[cycleMember[s[i] - 'a']]);
  }
  vector<double> secondTest = multiply(P, Q);
  for (int i = 0, colchin = P.size() - Q.size() + 1; i < colchin; ++i) {
    if (firstTest[i + s.size()] >= s.size() &&
        abs(secondTest[i + Q.size() - 1] - expected) <= 0.01) {
      cout << "1";
    } else {
      cout << "0";
    }
  }
  cout << "\n";
  return 0;
}
