Областная олимпиада по информатике 2022 года за 9 класс | Казахстанские олимпиады

Задача C. Восстановление строки

Вам дана строка $s$ длины $n$, состоящая из строчных латинских букв и символов '?'. Также, вам даны $m$ условий. Каждое условие описывается тремя целыми числами $l_1$, $l_2$ и $x$, которые означают что подстрока ($s_{l_1}$ $\ldots$ $s_{l_1+x-1}$) должна быть равна подстроке ($s_{l_2}$ $\ldots$ $s_{l_2+x-1}$).

Вам нужно заменить каждый символ '?' на строчную латинскую букву так чтобы выполнялись все $m$ условия. Среди всех таких строк, найдите лексикографически минимальную.

Строка $a$ лексикографический меньше строки $b$, если

• либо первые $k$ символов этих строк совпадают, а k $+$ 1-й символ в $a$ алфавитном порядке идет раньше k $+$ 1-го символа строки $b$. Например, abcdef < abdaaaa, так как первые два символа совпадают, а третья буква первой строки($c$) в алфавитном порядке идет раньше третьей буквы второй строки($d$).
• либо строка $a$ является префиксом строки $b$. Например, abc < abcde.
<

Формат входного файла

В первой строке находится одно целое число n($1$ $\le$ $n$ $\le$ $300000$).

Во второй строке находится строка $s$, состоящая из $n$ строчных латинских букв и символов '?'.

В третьей строке находится одно целое число m($1$ $\le$ $m$ $\le$ $300000$).

В следующих $m$ строках записаны по три целых числа $l_1$, $l_2$ и $x$ ($1$ $\le$ $l_1$, $l_2$ $\le$ $n$ $-$ $x$ $+$ $1$), означающие что подстрока ($s_{l_1}$ $\ldots$ $s_{l_1+x-1}$) равна подстроке ($s_{l_2}$ $\ldots$ $s_{l_2+x-1}$).

Формат выходного файла

Выведите лексикографически минимальную строку, которая удовлетворяет всем условиям, либо $-1$, если такой строки не существует.

Примеры

Входные данные

Выходные данные