CF568C New Language

Living in Byteland was good enough to begin with, but the good king decided to please his subjects and to introduce a national language. He gathered the best of wise men, and sent an expedition to faraway countries, so that they would find out all about how a language should be designed. After some time, the wise men returned from the trip even wiser. They locked up for six months in the dining room, after which they said to the king: "there are a lot of different languages, but almost all of them have letters that are divided into vowels and consonants; in a word, vowels and consonants must be combined correctly." There are very many rules, all of them have exceptions, but our language will be deprived of such defects! We propose to introduce a set of formal rules of combining vowels and consonants, and include in the language all the words that satisfy them. The rules of composing words are: - The letters are divided into vowels and consonants in some certain way; - All words have a length of exactly $ n $ ; - There are $ m $ rules of the form ( $ pos_{1},t_{1},pos_{2},t_{2} $ ). Each rule is: if the position $ pos_{1} $ has a letter of type $ t_{1} $ , then the position $ pos_{2} $ has a letter of type $ t_{2} $ . You are given some string $ s $ of length $ n $ , it is not necessarily a correct word of the new language. Among all the words of the language that lexicographically not smaller than the string $ s $ , find the minimal one in lexicographic order.

N/A

N/A

In the first test word "aa" is not a word of the language, but word "ab" is. In the second test out of all four possibilities only word "bb" is not a word of a language, but all other words are lexicographically less, so there is no answer. In the third test, due to the last rule, "abac" doesn't belong to the language ("a" is a vowel, "c" is a consonant). The only word with prefix "ab" that meets the given rules is "abaa". But it is less than "abac", so the answer will be "acaa"