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

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

Ограничение по времени Ограничение по памяти
3 секунды 256 мегабайт

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

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

Строка aa лексикографический меньше строки bb, если

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

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

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

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

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

    В следующих mm строках записаны по три целых числа l1l_1, l2l_2 и xx ($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-1, если такой строки не существует.

    Примеры

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

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