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