给你一个排列 $$$p$$$,由 $$$1$$$ 到 $$$26$$$ 之间的 $$$26$$$ 整数组成(因为它是一个排列,从 $$$1$$$ 到 $$$26$$$ 的每个整数在 $$$p$$$ 中恰好出现一次)和两个字符串 $$$s$$$ 和 $$$t$$$ 组成小写拉丁字母。
如果满足以下条件,则字符串 $$$t$$$ 的子字符串 $$$t'$$$ 是字符串 $$$s$$$ 的出现:
1. $$$|t'| = |s|$$$;
2. 对于 [1, |s|]$$$ 中的每个 $$$i \in,$$$s_i = t'_i$$$ 或 $$$p_{idx(s_i)} = idx(t'_i)$$$,其中 $$$idx(c)$$$ 是字符 $$$c$$$ 在拉丁字母中的索引($$$idx(\text{a}) = 1$$$, $$$idx(\text{b}) = 2$$$, $$$idx(\text{z}) = 26$$$)。
例如,如果 $$$p_1 = 2$$$、$$$p_2 = 3$$$、$$$p_3 = 1$$$、$$$s = \text{abc}$$$、$$$t = \text{abcaaba}$$$,则 $$$t$$$ 的三个子串是 $$$s$$$ 的出现(它们是$$$t' = \text{abc}$$$、$$$t' = \text{bca}$$$ 和 $$$t' = \text{aba}$$$)。
对于$$$t$$$ 中长度等于$$$|s|$$$ 的每个子串,检查它是否出现$$$s$$$。
输入
第一行包含 $$$26$$$ 整数 $$$p_1$$$, $$$p_2$$$, ..., $$$p_{26}$$$ ($$$1 \le p_i \le 26$$$,所有这些整数都是成对不同的)。
第二行包含一个字符串 $$$s$$$,第三行包含一个字符串 $$$t$$$ ($$$2 \le |s| \le |t| \le 2 \cdot 10^5$$$),均由小写拉丁字母组成。
输出
打印字符串 $$$|t| - |s| + 1$$$ 个字符,每个字符应为 0 或 1。当且仅当 $$$t$$$ 中以第 $$$i$$$ 字符开头并以第 $$$(i + |s| - 1)$$$ 个字符(含)结尾的子字符串出现 $$$s$$$ 时,第 $$$i$$$ 字符应为 1。
示例
输入 #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