Background

Translated from ROI 2021 D1T2。

Problem Description

You are given a sequence of $n$ crystals arranged from left to right. Each crystal belongs to one of $k$ types, denoted by the first $k$ lowercase English letters. Therefore, the crystal sequence can be represented as a string of lowercase letters.

In one move of the game, you may remove one crystal from the sequence. The player's goal is to obtain the lexicographically smallest string using the allowed deletions.

The allowed deletions are defined by a $k \times k$ table $A$, whose entries are only $0$ and $1$. If $A_{i,j} = 1$, it means that when the crystal immediately in front of it is of type $i$, it is allowed to delete a crystal of type $j$. These operations may be performed in any order.

A string $x$ is lexicographically smaller than a string $y$ if at least one of the following holds:

• There exists a position $m$ that exists in both strings, and before position $m$ the two strings are identical, but the $m$-th character of $x$ is smaller than the $m$-th character of $y$.
• String $x$ is a strict prefix of string $y$ (i.e., it can be obtained by deleting one or more characters from the end of $y$).

For example, ccf is lexicographically smaller than cff because the $2$-nd character of ccf (c) is smaller than the $2$-nd character of cff (f). Also, noi is lexicographically smaller than noip because noi is a strict prefix of noip.

Input Format

The first line contains two integers $k$ and $n$ ($1 \le k \le 26,1 \le n \le 500000$), representing the number of crystal types and the length of the initial crystal sequence.

The next $k$ lines give the table $A$. The $i$-th line contains $k$ characters, each being 0 or 1. The character in row $i$ and column $j$ is $A_{ij}$.

The last line is a string of $n$ lowercase English letters, representing the initial crystal sequence. It is guaranteed that the string contains only the first $k$ letters (for example, the first seven letters are a, b, c, d, e, f, g). The $i$-th letter represents the $i$-th type of crystal.

Output Format

Output the lexicographically smallest string that can be obtained through the operations.

3 7
010
001
100
abacaba

aac

3 5
010
001
100
bcacb

bacb

Hint

Sample Explanation:

The two samples have the same $A$. They both allow only the following three types of deletions (the underlined character is the previous character, and the struck-out character is the deleted one): $\underline{\text{a}}\xcancel{\text{b}},\underline{\text{b}}\xcancel{\text{c}},\underline{\text{c}}\xcancel{\text{a}}$.

In sample $1$, you can delete as follows:

In sample $2$, you can delete as follows:

• $\text{bcacb}$
• $\underline{\text{b}}\xcancel{\text{c}}\text{acb}$
• $\text{bacb}$

Constraints:

For $100\%$ of the testdata, $n \le 500000$ and $k \le 26$。

Translated by ChatGPT 5