codeforces#P1334G. Substring Search

Substring Search

Description

You are given a permutation pp consisting of exactly 2626 integers from 11 to 2626 (since it is a permutation, each integer from 11 to 2626 occurs in pp exactly once) and two strings ss and tt consisting of lowercase Latin letters.

A substring tt' of string tt is an occurence of string ss if the following conditions are met:

  1. t=s|t'| = |s|;
  2. for each i[1,s]i \in [1, |s|], either si=tis_i = t'_i, or pidx(si)=idx(ti)p_{idx(s_i)} = idx(t'_i), where idx(c)idx(c) is the index of character cc in Latin alphabet (idx(a)=1idx(\text{a}) = 1, idx(b)=2idx(\text{b}) = 2, idx(z)=26idx(\text{z}) = 26).

For example, if p1=2p_1 = 2, p2=3p_2 = 3, p3=1p_3 = 1, s=abcs = \text{abc}, t=abcaabat = \text{abcaaba}, then three substrings of tt are occurences of ss (they are t=abct' = \text{abc}, t=bcat' = \text{bca} and t=abat' = \text{aba}).

For each substring of tt having length equal to s|s|, check if it is an occurence of ss.

The first line contains 2626 integers p1p_1, p2p_2, ..., p26p_{26} (1pi261 \le p_i \le 26, all these integers are pairwise distinct).

The second line contains one string ss, and the third line contains one string tt (2st21052 \le |s| \le |t| \le 2 \cdot 10^5) both consisting of lowercase Latin letters.

Print a string of ts+1|t| - |s| + 1 characters, each character should be either 0 or 1. The ii-th character should be 1 if and only if the substring of tt starting with the ii-th character and ending with the (i+s1)(i + |s| - 1)-th character (inclusive) is an occurence of ss.

Input

The first line contains 2626 integers p1p_1, p2p_2, ..., p26p_{26} (1pi261 \le p_i \le 26, all these integers are pairwise distinct).

The second line contains one string ss, and the third line contains one string tt (2st21052 \le |s| \le |t| \le 2 \cdot 10^5) both consisting of lowercase Latin letters.

Output

Print a string of ts+1|t| - |s| + 1 characters, each character should be either 0 or 1. The ii-th character should be 1 if and only if the substring of tt starting with the ii-th character and ending with the (i+s1)(i + |s| - 1)-th character (inclusive) is an occurence of ss.

Samples

输入数据 1

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

输出数据 1

11001