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 PI = acos(-1.0);
struct Complex {
  long double x, y;
  Complex(long double _x = 0.0, long double _y = 0.0) {
    x = _x;
    y = _y;
  }
  Complex operator-(const Complex &b) const {
    return Complex(x - b.x, y - b.y);
  }
  Complex operator+(const Complex &b) const {
    return Complex(x + b.x, y + b.y);
  }
  Complex operator*(const Complex &b) const {
    return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
  }
};
void change(Complex y[], int len) {
  int i, j, k;
  for (i = 1, j = len / 2; i < len - 1; i++) {
    if (i < j) swap(y[i], y[j]);
    k = len / 2;
    while (j >= k) {
      j -= k;
      k /= 2;
    }
    if (j < k) j += k;
  }
}
void fft(Complex y[], int len, int on) {
  change(y, len);
  for (int h = 2; h <= len; h <<= 1) {
    Complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h));
    for (int j = 0; j < len; j += h) {
      Complex w(1, 0);
      for (int k = j; k < j + h / 2; k++) {
        Complex u = y[k];
        Complex t = w * y[k + h / 2];
        y[k] = u + t;
        y[k + h / 2] = u - t;
        w = w * wn;
      }
    }
  }
  if (on == -1)
    for (int i = 0; i < len; i++) y[i].x /= len;
}
const int MAXN = 800010;
Complex x1[MAXN], x2[MAXN];
void output(vector<int> vec) {
  for (int i = 0; i < vec.size(); i++) printf("%d ", vec[i]);
  printf("\n");
}
void output(vector<long long> vec) {
  for (int i = 0; i < vec.size(); i++) printf("%I64d ", vec[i]);
  printf("\n");
}
vector<long long> multiply(vector<int> a, vector<int> b) {
  int sz1 = a.size();
  int sz2 = b.size();
  int len = 1;
  while (len < sz1 * 2 || len < sz2 * 2) len <<= 1;
  for (int i = 0; i < sz1; i++) {
    x1[i] = Complex(a[i], 0);
  }
  for (int i = sz1; i < len; i++) {
    x1[i] = Complex(0, 0);
  }
  for (int i = 0; i < sz2; i++) {
    x2[i] = Complex(b[i], 0);
  }
  for (int i = sz2; i < len; i++) {
    x2[i] = Complex(0, 0);
  }
  fft(x1, len, 1);
  fft(x2, len, 1);
  for (int i = 0; i < len; i++) {
    x1[i] = x1[i] * x2[i];
  }
  fft(x1, len, -1);
  vector<long long> vec;
  for (int i = 0; i < len; i++) {
    if (x1[i].x >= 0)
      vec.push_back((long long)(x1[i].x + 0.5));
    else
      vec.push_back((long long)(x1[i].x - 0.5));
    double tmp1 = x1[i].x;
    long long t1;
    if (tmp1 >= 0)
      t1 = (long long)(x1[i].x + 0.5);
    else
      t1 = (long long)(x1[i].x - 0.5);
    if (fabs(t1 - tmp1) > 0.6) printf("%.10f\n", tmp1);
  }
  return vec;
}
char s[MAXN], t[MAXN];
int p[30];
long long S[MAXN];
int main() {
  for (int i = 0; i < 26; i++) {
    scanf("%d", &p[i]);
    p[i]--;
  }
  scanf("%s%s", s, t);
  int n = strlen(s);
  int m = strlen(t);
  vector<int> A, B, C;
  long long tmp = 0;
  for (int i = 0; i < n; i++) {
    int t1 = (s[n - 1 - i] - 'a');
    int t2 = p[t1];
    t1 -= 13;
    t2 -= 13;
    A.push_back(-2 * t1 - 2 * t2);
    B.push_back(t1 * t1 + t2 * t2 + 4 * t1 * t2);
    C.push_back(-2 * t1 * t2 * t2 - 2 * t1 * t1 * t2);
    tmp += t1 * t1 * t2 * t2;
  }
  vector<int> tb1, tb2, tb3;
  for (int i = 0; i < m; i++) {
    int t1 = t[i] - 'a' - 13;
    tb1.push_back(t1);
    tb2.push_back(t1 * t1);
    tb3.push_back(t1 * t1 * t1);
  }
  vector<long long> tb_A = multiply(tb3, A);
  vector<long long> tb_B = multiply(tb2, B);
  vector<long long> tb_C = multiply(tb1, C);
  for (int i = 0; i < m - n + 1; i++) {
    S[i] = tb_A[i + n - 1] + tb_B[i + n - 1] + tb_C[i + n - 1] + tmp;
  }
  tmp = 0;
  for (int i = 0; i < n - 1; i++) {
    int t1 = t[i] - 'a' - 13;
    tmp += t1 * t1 * t1 * t1;
  }
  for (int i = 0; i < m - n + 1; i++) {
    int t1 = t[i + n - 1] - 'a' - 13;
    tmp += t1 * t1 * t1 * t1;
    S[i] += tmp;
    int t2 = t[i] - 'a' - 13;
    tmp -= t2 * t2 * t2 * t2;
  }
  for (int i = 0; i < m - n + 1; i++) {
    if (S[i] == 0)
      printf("1");
    else
      printf("0");
  }
  printf("\n");
  return 0;
}
