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
import java.io.*;
import java.util.*;

public class G
{
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok;

    public void go() throws IOException
    {
        // in = new BufferedReader(new FileReader(new File("test.txt")));
        ntok();
        int[] next = iapar(26);
        int[] comp = new int[26];
        int[] index = new int[26];
        int[] sizes = new int[26];
        int numComp = 0;
        Arrays.fill(comp, -1);
        for (int i = 0; i < 26; i++) {
            if (comp[i] == -1) {
                int curr = i;
                int size = 0;
                while (comp[curr] == -1) {
                    comp[curr] = numComp;
                    index[curr] = size;
                    curr = next[curr]-1;
                    size++;
                }
                for (int e = 0; e < size; e++) {
                    sizes[curr] = size;
                    curr = next[curr]-1;
                }
                numComp++;
            }
        }
        // out.println(Arrays.toString(comp));
        // out.println(Arrays.toString(index));
        // out.println(Arrays.toString(sizes));
        ntok();
        char[] t = spar().toCharArray();
        ntok();
        char[] s = spar().toCharArray();
        int n = s.length;
        int m = t.length;
        boolean[] ans = new boolean[n-m+1];
        Arrays.fill(ans, true);

        sameCompTest(s, t, ans, comp);
        validCharsTest(s, t, ans, index, sizes);

        for (int i = 0; i < ans.length; i++) {
            out.print(ans[i] ? '1' : '0');
        }
        out.println();

        // boolean[] checker = new boolean[n-m+1];
        // Arrays.fill(checker, true);
        // brute(s, t, checker, next);
        // for (int i = 0; i < ans.length; i++) {
        //     if (ans[i] != checker[i]) {
        //         out.println("INCORRECT, index " + i);
        //         // out.print("brute force: ");
        //         // for (boolean b : checker) {
        //         //     out.print(b ? '1' : '0');
        //         // }
        //         // out.println();
        //         break;
        //     }
        // }

        out.flush();
        in.close();
    }

    public void brute(char[] s, char[] t, boolean[] ans, int[] next) {
        int n = s.length;
        int m = t.length;
        for (int offset = 0; offset < n-m+1; offset++) {
            boolean works = true;
            for (int i = 0; i < m; i++) {
                if (s[offset+i] != t[i] && s[offset+i]-'a' != next[t[i]-'a']-1) {
                    works = false;
                }
            }
            ans[offset] = works;
        }
    }

    public void sameCompTest(char[] s, char[] t, boolean[] ans, int[] comp) {
        int n = s.length;
        int m = t.length;
        int[] ss = new int[n];
        for (int i = 0; i < n; i++) {
            ss[i] = comp[s[i]-'a'];
        }
        int[] tt = new int[m];
        for (int i = 0; i < m; i++) {
            tt[i] = comp[t[i]-'a'];
        }
        // System.out.println(Arrays.toString(ss));
        // System.out.println(Arrays.toString(tt));
        int[] lps = new int[m];
        lps[0] = 0;
        int i = 1;
        int len = 0;
        while (i < m) {
            if (tt[i] == tt[len]) {
                len++;
                lps[i] = len;
                i++;
            } else if (len != 0) {
                len = lps[len-1];
            } else {
                i++;
            }
        }
        // out.println(Arrays.toString(lps));
        i = 0;
        int j = 0;
        boolean[] sameComp = new boolean[ans.length];
        while (i < n) {
            if (ss[i] == tt[j]) {
                i++;
                j++;
                if (j == m) {
                    sameComp[i-j] = true;
                    j = lps[j-1];
                }
            } else if (j != 0) {
                j = lps[j-1];
            } else {
                i++;
            }
        }
        for (i = 0; i < ans.length; i++) {
            ans[i] &= sameComp[i];
        }
    }

    public void validCharsTest(char[] s, char[] t, boolean[] ans, int[] index, int[] sizes) {
        int n = s.length;
        int m = t.length;
        int nn = 1;
        while (nn < n+m) {
            nn *= 2;
        }
        Complex[] fa = new Complex[nn];
        Complex[] fb = new Complex[nn];
        double[][] cos1 = new double[26][27];
        for (int i = 0; i < 26; i++) {
            for (int e = 1; e < 27; e++) {
                cos1[i][e] = Math.cos(Math.PI * 2 * i / e);
            }
        }
        double[][] sin1 = new double[26][27];
        for (int i = 0; i < 26; i++) {
            for (int e = 1; e < 27; e++) {
                sin1[i][e] = Math.sin(Math.PI * 2 * i / e);
            }
        }
        double[][] cos2 = new double[26][27];
        for (int i = 0; i < 26; i++) {
            for (int e = 1; e < 27; e++) {
                cos2[i][e] = Math.cos((-Math.PI * 2 * i - Math.PI) / e);
            }
        }
        double[][] sin2 = new double[26][27];
        for (int i = 0; i < 26; i++) {
            for (int e = 1; e < 27; e++) {
                sin2[i][e] = Math.sin((-Math.PI * 2 * i - Math.PI) / e);
            }
        }
        for (int i = 0; i < nn; i++) {
            if (i < n) {
                fa[i] = new Complex(cos1[index[s[i]-'a']][sizes[s[i]-'a']], sin1[index[s[i]-'a']][sizes[s[i]-'a']]);
            } else {
                fa[i] = new Complex();
            }
        }
        for (int i = 0; i < nn; i++) {
            if (i < m) {
                fb[i] = new Complex(cos2[index[t[m-i-1]-'a']][sizes[t[m-i-1]-'a']], sin2[index[t[m-i-1]-'a']][sizes[t[m-i-1]-'a']]);
            } else {
                fb[i] = new Complex();
            }
        }
        // out.println(Arrays.toString(fa));
        // out.println(Arrays.toString(fb));
        fft(fa, false);
        fft(fb, false);
        for (int i = 0; i < nn; i++) {
            fa[i].multiply(fb[i]);
        }
        fft(fa, true);
        // out.println(Arrays.toString(fa));
        double[] cos3 = new double[27];
        for (int i = 1; i < 27; i++) {
            cos3[i] = Math.cos(Math.PI / i);
        }
        double target = 0;
        for (int i = 0; i < m-1; i++) {
            target += cos3[sizes[s[i]-'a']];
        }
        for (int i = 0; i < n-m+1; i++) {
            target += cos3[sizes[s[i+m-1]-'a']];
            ans[i] &= Math.abs(target - fa[i+m-1].a) < 0.0001;
            // out.println(Math.abs(target - fa[i+m-1].a) + " " + target + " " + fa[i+m-1].a);
            target -= cos3[sizes[s[i]-'a']];
        }
    }

    public void fft(Complex[] f, boolean inverse) {
        int n = f.length;
        int numBits = 0;
        while (1 << numBits < n) {
            numBits++;
        }
        for (int i = 0; i < n; i++) {
            int rev = reverseBits(i, numBits);
            if (i < rev) {
                Complex temp = f[i];
                f[i] = f[rev];
                f[rev] = temp;
            }
        }

        Complex w = new Complex();
        Complex temp = new Complex();
        Complex rot = new Complex();
        for (int len = 2; len <= n; len *= 2) {
            double angle = Math.PI * 2 / len * (inverse ? -1 : 1);
            rot.a = Math.cos(angle);
            rot.b = Math.sin(angle);
            for (int offset = 0; offset < n; offset += len) {
                w.a = 1;
                w.b = 0;
                for (int i = 0; i*2 < len; i++) {
                    temp.set(f[offset + i+len/2]);
                    temp.multiply(w);
                    f[offset + i+len/2].set(f[offset + i]);
                    f[offset + i+len/2].subtract(temp);
                    f[offset + i].add(temp);
                    w.multiply(rot);
                }
            }
        }

        if (inverse) {
            for (Complex c : f) {
                c.a /= n;
                c.b /= n;
            }
        }
    }

    public int reverseBits(int n, int numBits) {
        int rev = 0;
        for (int i = 0; i < numBits; i++) {
            rev *= 2;
            rev += n%2;
            n /= 2;
        }
        return rev;
    }

    private class Complex {
        double a, b;

        public Complex() {}

        public Complex(double a, double b) {
            this.a = a;
            this.b = b;
        }

        public void multiply(Complex other) {
            double aa = a * other.a - b * other.b;
            double bb = a * other.b + b * other.a;
            a = aa;
            b = bb;
        }

        public void add(Complex other) {
            a += other.a;
            b += other.b;
        }

        public void subtract(Complex other) {
            a -= other.a;
            b -= other.b;
        }

        public void set(Complex other) {
            a = other.a;
            b = other.b;
        }

        public String toString() {
            return String.format("(%.3f, %.3f)", a, b);
        }
    }

    public void ntok() throws IOException
    {
        tok = new StringTokenizer(in.readLine());
    }

    public int ipar()
    {
        return Integer.parseInt(tok.nextToken());
    }

    public int[] iapar(int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar()
    {
        return Long.parseLong(tok.nextToken());
    }

    public long[] lapar(int n)
    {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar()
    {
        return Double.parseDouble(tok.nextToken());
    }

    public String spar()
    {
        return tok.nextToken();
    }

    public static void main(String[] args) throws IOException
    {
        new G().go();
    }
}
