Война континента Bezorath против вторжения армии демонов зашла в тупик. Эльфы, из поколения в поколение живущие на этом континенте, начали искать артефакты, оставленные древними богами, в надежде, что их таинственная сила поможет им победить армию демонов.
Заплатив огромную цену, эльфы добыли хорошо сохранившийся магический жезл с древнего поля битвы. Однако после «Войны Рагнарёка», которую все исторические хроники считают запретной темой, магические камни, инкрустированные в жезл, были повреждены, а его сила почти иссякла. Высший совет эльфов принял решение собрать все сохранившиеся магические камни и назначил щедрую награду любому мастеру, способному восстановить этот жезл.
Как пятьсот первый наследник магического искусства, вы приняли эту трудную и священную миссию. На жезле слева направо инкрустировано $n$ магических камней. Всего существует $10$ видов магических камней, обозначаемых цифрами 0123456789. Некоторые позиции повреждены и обозначены символом .. Вам необходимо заполнить каждое поврежденное место подходящим магическим камнем (количество камней каждого вида не ограничено, но нельзя заменять уже существующие неповрежденные камни). В древней магической книге записано $m$ видов заклинаний $(S_i, V_i)$, где $S_i$ — непустая строка из цифр, а $V_i$ — магическая сила, которую вызывает данная комбинация.
Начальное значение магической силы жезла $\mathrm{Magic} = 1$. Каждый раз, когда в жезле встречается непрерывная последовательность камней, равная $S_i$, значение $\mathrm{Magic}$ умножается на $V_i$. Однако, если жезл содержит слишком много заклинаний, он теряет чистоту, что снижает его силу: пусть $c$ — общее количество заклинаний, содержащихся в жезле (если категории заклинаний совпадают, но встречаются в разных позициях, они считаются отдельно). Итоговое значение магической силы жезла равно $\sqrt[c]{\mathrm{Magic}}$. (Если $c = 0$, итоговое значение магической силы равно $1$.)
Например, если есть два заклинания $(01, 3)$ и $(10, 4)$, то магическая сила жезла 0101 равна $\sqrt[3]{ 3 \times 4 \times 3}$.
Вам необходимо максимизировать итоговую магическую силу восстановленного жезла. Выведите любой подходящий вариант.
Входные данные
Первая строка содержит два целых положительных числа $n$ и $m$, обозначающие количество камней и количество заклинаний.
Вторая строка содержит строку $T$ длины $n$, представляющую начальное состояние жезла.
Следующие $m$ строк содержат по одной непустой строке из цифр $S_i$ и одному положительному целому числу $V_i$, описывающим каждое заклинание.
Выходные данные
Выведите строку, представляющую камни на восстановленном жезле слева направо. Если существует несколько решений, выведите любое из них.
Примеры
Пример 1
4 3 .... 1 2 2 2 3 1
Выходные данные
2019
Примечание
Итоговая магическая сила жезла равна $2$.
Пример 2
5 4 ..0.. 0 2 00 2 01 4 10 3
Выходные данные
11012
Примечание
Итоговая магическая сила жезла равна $\sqrt[3]{2 \times 3 \times 4}$.
Пример 3
18 6 ...2.1.0.1..1.0..1 011 6 111 4 010 12 121 7 101 5 10 3
Выходные данные
121211203112120121
Подзадачи
Пусть $s = \sum_{i=1}^{m} |S_i|$ — сумма длин всех строк заклинаний.
| Тест | $n\le$ | $s\le$ | Особые свойства |
|---|---|---|---|
| $1\sim 3$ | $6$ | $20$ | |
| $4\sim 5$ | $501$ | $5$ | |
| $6$ | $501$ | $501$ | Все $V_i$ одинаковы |
| $7$ | $501$ | $501$ | $V_i$ принимают не более $2$ различных значений |
| $8$ | $501$ | $501$ | $V_i$ принимают не более $3$ различных значений |
| $9\sim 11$ | $501$ | $501$ | $T$ полностью состоит из . |
| $12\sim 13$ | $501$ | $501$ | В $T$ не более $3$ позиций с . |
| $14\sim 16$ | $501$ | $501$ | |
| $17\sim 20$ | $1501$ | $1501$ |
Для $100\%$ данных выполняются условия: $1\le n, m, s \le 1501$, $1\le V_i\le 10^9$.