시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB2510731.818%

문제

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

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

서브태스크

번호배점제한
110

$n \le 20$, $k \le 26$

212

$n \le 50$, $k \le 5$

316

$n \le 300$, $k \le 5$

417

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

510

$n \le 2\,000$, $k \le 26$

69

$n \le 10\,000$, $k \le 26$

78

$n \le 100\,000$, $k \le 26$

811

$n \le 500\,000$, $k \le 2$

97

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

예제 입력 1

3 7
010
001
100
abacaba

예제 출력 1

aac

예제 입력 2

3 5
010
001
100
bcacb

예제 출력 2

bacb

힌트

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

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

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

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

  • bcacb
  • bcacb
  • bacb

채점 및 기타 정보

  • 예제는 채점하지 않는다.