Пере-конструкция Суффиксного Массива
Был долгий день на вашей новой работе. Вы провели его, оптимизируя ключевые структуры данных Суффиксного Массивa для вашего нового работодателя, GCPC ([G]lobal Suffix [C]ollecting and [P]rocessing [C]ollective). Когда вы уже собирались выключить компьютер, заметили, что тестовый запуск показал повреждение значительных частей важной информации. К сожалению, резервные серверы компании вышли из строя вчера, и теперь вы рискуете потерять ценные Суффиксные Массивы.
При проверке данных вы обнаружили, что ситуация почти катастрофическая. Множество суффиксов отсутствует, а оставшиеся могут быть повреждены. Вы нашли примеры, где части букв заменены случайными символами, а в некоторых местах обнаружили символ '*', который использовали как заполнитель в программном обеспечении. Этот заполнитель заменил произвольно большую подстроку. Более того, некоторые строки оказались несогласованными, и неясно, какая версия символа правильная. Ваша единственная надежда — надеяться и молиться, что восстановление возможно.
Данные представлены в виде списка суффиксов с указанием начальной позиции каждого суффикса. У вас также есть список длин всех наборов данных, которые есть в наличии у компании. Можете ли вы восстановить хотя бы базовые строки? Если да, то можно было бы запустить один из новых алгоритмов Суффиксного Массивa, чтобы восстановить полный набор данных.
Входные данные
Каждый набор тестов состоит из нескольких тестовых случаев t (0 < t ≤ 100). Количество тестовых случаев указано в первой строке ввода. Каждый тестовый случай описывается следующим образом. В первой строке указана длина l желаемой выходной строки и количество (частично поврежденных) суффиксов s (1 ≤ l ≤ 10000; 1 ≤ s ≤ 10000). Затем следуют s строк, каждая из которых указывает позицию p суффикса в строке и сам суффикс (1 ≤ p ≤ l). Суффикс содержит только символы из набора {a, ..., z, A, ..., Z, ., *} (символ '.' не имеет специального значения). Общая сумма символов, предоставленных для суффиксов, не превышает 250000.
Выходные данные
Если восстановление потерянных данных возможно, напечатайте восстановленное предложение. В противном случае напечатайте "IMPOSSIBLE" в одной строке. Восстановление возможно только в том случае, если множество возможных символов для каждой позиции в строке содержит ровно один символ.