eolymp
bolt
Try our new interface for solving problems

Игра

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Дедушка Марат очень любит свою внучку Машу. Тем более, что из всей его семьи она самая младшая. Поэтому он часто играет с ней в разные игры.

Сегодня, например, они играли в развивающую мышление игру, которая называется "Угадай слово". Правила игры достаточно просты:

  • Сначала Дедушка загадывает слово. Словом считается любая последовательность из строчныхлатинских символов. Единственное ограничение - это слово должно быть палиндромом. Напомним, строка S длины n называется палиндромом, если

    i

    [1, n]: S[i] = S[n - i + 1].

  • За один ход Маша может выбрать произвольное слово P и дописать P к S слева или справа.

  • Если полученная строка не является палиндромом, то дедушка говорит об этом Маше и игра заканчивается

  • Если полученная строка все еще палиндром, то игра продолжается

  • Когда игра закончилась, Маша должна назвать загаданное слово

Дедушка записал все ходы своей внучки за всю игру. Теперь же он хочет вспомнить, чем закончилась игра. Если Маша отгадала слово, то он хочет определить, какое оно было. Иначе определить, не угадала она из-за того, что у нее оставалось несколько вариантов, или из-за того, что он ошибся в процессе игры.

Giriş verilənləri

Первая строка входного файла содержит два целых числа n и m (1n, m3000) - длину загаданного слова и количество ходов в игре, соответственно.

Следующие m строк содержат по одному слову s_i, состоящему из строчных латинских букв - слово, выбранное Машей на i-м ходу. Сумма длин всех s_i не превышает 3000.

Последняя строка содержит слово w из m символов L или R. w_i = L если слово s_i было записано слева от текущей строки на i-м ходу, w_i = R - если справа.

Çıxış verilənləri

В выходной файл выведите слово Unique, если Маша может однозначно установить, какое слово загадал дедушка, Ambiguou - если таких слов могло быть несколько, либо Impossible - если таких слов не существует и дедушка ошибся.

Nümunə

Giriş verilənləri #1
3 2
a
a
LR
Çıxış verilənləri #1
Impossible
Müəllif А.Цыпленков, П.Кротков
Mənbə Четвертая олимпиада, Базовый уровень. 12 ноября 2011 года.