Родные просторы

Вы играете на смартфоне в игру <<Родные просторы>>, в которой управляющий Остап помогает помещику восстановить отцовский дом. Игра происходит следующим образом. 

Дана последовательность из $n$ кристаллов, расположенных в один ряд слева направо. Каждый кристалл относится к одному из $k$ видов, обозначенных первыми $k$ английскими буквами. Таким образом, последовательность кристаллов записывается строкой английских букв.

За один ход игры можно удалить из последовательности один кристалл. Цель игрока --- получить в результате применения разрешенных видов удалений лексикографически минимально возможную строку.

Разрешённые виды удаления кристаллов заданы таблицей $A$ размера $k\times k$ из нулей и единиц. Если $A\_{ij}=1$, то разрешается удалить кристалл вида $j$, если непосредственно слева от него находится кристалл вида $i$. Данные действия можно выполнять в любом порядке.

Напомним, что строка $x$ лексикографически меньше строки $y$, если выполнено одно из двух условий:

• существует такая позиция символа $m$, присутствующая в обеих строках, что до $m$-го символа строки совпадают, а $m$-й символ строки $x$ меньше $m$-го символа $y$,
• строка $x$ является строгим префиксом $y$ (то есть получается отбрасыванием одного или больше символов с конца строки $y$).

В первой строке даны два целых числа $k$ и $n$ ($1 \le k \le 26$, $1 \le n \le 500\\,000$) --- количество видов кристаллов и длина исходной последовательности кристаллов.

В следующих $k$ строках задана таблица $A$, $i$-я строка содержит ровно $k$ символов $0$ или $1$. Символ в $i$-й строке на $j$-й позиции равен $A\_{ij}$.

В последней строке записаны $n$ строчных английских букв, задающие исходную последовательность кристаллов. Гарантируется, что в строке встречаются только первые $k$ букв английского алфавита, $i$-я по счёту буква английского алфавита обозначает $i$-й вид кристаллов.

Выведите лексикографически минимальную строку, которую можно получить из исходной строки разрешёнными действиям.

• $n \le 500\\,000$
• $k \le 26$

В примерах из условия разрешены следующие виды удалений (удаляемый символ зачёркнут, символ непосредственно перед ним подчёркнут): ab, bc, ca.

Возможная последовательность удалений в первом примере:

• abacaba
• abacaba
• abacaa
• abacaa
• abaca
• abaca
• abac
• abac
• aac

Возможная последовательность удалений во втором примере:

• bcacb
• bcacb
• bacb