21546번 - Родные просторы 서브태스크다국어

문제

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

Дана последовательность из $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$

서브태스크

힌트

В примерах из условия разрешены следующие виды удалений (удаляемый символ зачёркнут, символ непосредственно перед ним подчёркнут): a(削除) b (削除ここまで), b(削除) c (削除ここまで), c(削除) a (削除ここまで).

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

• abacaba
• abaca(削除) b (削除ここまで)a
• abacaa
• abac(削除) a (削除ここまで)a
• abaca
• abac(削除) a (削除ここまで)
• abac
• a(削除) b (削除ここまで)ac
• aac

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

• bcacb
• b(削除) c (削除ここまで)acb
• bacb