G. Поиск подстроки
ограничение по времени на тест
1.25 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана перестановка $$$p$$$, состоящая из $$$26$$$ целых чисел от $$$1$$$ до $$$26$$$ (так как это перестановка, каждое число от $$$1$$$ до $$$26$$$ встречается в $$$p$$$ ровно один раз), а также две строки $$$s$$$ и $$$t$$$, состоящие из строчных букв латинского алфавита.

Подстрока $$$t'$$$ строки $$$t$$$ является вхождением строки $$$s$$$, если выполняются следующие условия:

  1. $$$|t'| = |s|$$$;
  2. для каждого $$$i \in [1, |s|]$$$ либо $$$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. $$$i$$$-й символ должен быть 1 тогда и только тогда, когда подстрока $$$t$$$, начинающаяся с $$$i$$$-го символа и заканчивающаяся $$$(i + |s| - 1)$$$-м символом (включительно), является вхождением строки $$$s$$$.

Пример
Входные данные
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
Выходные данные
11001