P11089 [ROI 2021] Mobile Game (Day 1)

Translated from [ROI 2021 D1T2](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day1.pdf)。

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`.

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 the lexicographically smallest string that can be obtained through the operations.

### 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: | Subtask | Score | $n\le$ | $k\le$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $20$ | $26$ | | $2$ | $12$ | $50$ | $5$ | | $3$ | $16$ | $300$ | $5$ | | $4$ | $17$ | $500$ | $26$ | | $5$ | $10$ | $2000$ | $26$ | | $6$ | $9$ | $10000$ | $26$ | | $7$ | $8$ | $100000$ | $26$ | | $8$ | $11$ | $500000$ | $2$ | | $9$ | $7$ | $500000$ | $26$ | For $100\%$ of the testdata, $n \le 500000$ and $k \le 26$。 Translated by ChatGPT 5