Рассмотрим множество S,
состоящее из N (1 <= N
<= 10) начальных букв латинского
алфавита. Введём на этом множестве бинарную операцию умножения при помощи
таблицы, т.е. каждой упорядоченной паре элементов из S поставим в
соответствие некоторый элемент из S. Например, пусть N = 2,
тогда
S = {a, b}. Возьмём таблицу
Первая строка этой таблицы
говорит о том, что a × a
= b и a × b
= a. Вторая строка означает, что b ×
a = b и b × b
= b. Таким образом мы задали таблицу умножения для множества S.
В дальнейшем мы будем опускать
символ умножения и вместо a ×
b будем писать просто ab. Умножение, заданное произвольной
таблицей, не обязано быть ни коммутативно — ab не обязано равняться ba,
ни ассоциативно — a(bc) не обязано равняться (ab)c.
Дано число N — количество
элементов множества, таблица умножения для этого множества, строка, состоящая
из маленьких латинских букв-элементов множества, а также задан некий элемент
множества. Ваша программа должна расставить в данной строке скобки так, чтобы
порядок умножения определялся однозначно, и результатом умножения был заданный
элемент.
Время тестирования:
1 секунда на один тест на Intel Celeron 2500.
Первая строка входного
файла содержит целое число N (1 <=
N <= 10). Вторая строка
содержит исходную строку из элементов множества. Гарантируется, что она будет
содержать только разрешённые строчные латинские буквы, и её длина не превзойдёт
100. В третьей строке задан символ-элемент множества, который нужно получить в
результате умножения. Следующие N строк содержат по N символов
каждая — это таблица умножения. Символы в строках заданы без пробелов.
Если можно расставить скобки как
требует того условие задачи, то в первой строке выходного файла выведите
"YES", в противном
случае — "NO"
(большими буквами, без кавычек). В случае положительного ответа во второй
строке выведите исходную строку с расставленными скобками. Скобки должны быть
расставлены корректно, и длина ответа не должна превышать 500 символов. Если
ответов несколько, выведите любой.
Примеры
|
STDIN
|
STDOUT
|
2
aabba
b
ba
bb
|
YES
(a(ab))(ba)
|
2
aabba
a
ba
bb
|
YES
(a((a(bb))a))
|
