E. Сопоставление шаблонов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ шаблонов $$$p_1, p_2, \dots, p_n$$$ и $$$m$$$ строк $$$s_1, s_2, \dots, s_m$$$. Каждый шаблон $$$p_i$$$ состоит из $$$k$$$ символов, каждый из которых — это либо строчная латинская буква или символ подчеркивания. Все шаблоны попарно различны. Каждая строка $$$s_j$$$ состоит из $$$k$$$ строчных латинских букв.

Строка $$$a$$$ подходит под шаблон $$$b$$$, если для каждого $$$i$$$ от $$$1$$$ до $$$k$$$ либо $$$b_i$$$ — это подчеркивание, либо $$$b_i=a_i$$$.

Вам требуется переупорядочить шаблоны таким образом, что первый шаблон, под который подходит $$$j$$$-я строка, — это $$$p[mt_j]$$$. Разрешается не изменять порядок шаблонов.

Можно ли осуществить такое переупорядочивание? Если можно, то выведите любой корректный порядок.

Входные данные

В первой строке записаны три целых числа $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m \le 10^5$$$, $$$1 \le k \le 4$$$) — количество шаблонов, количество строк и длина каждого шаблона и строки.

В каждой из следующих $$$n$$$ строк записан шаблон — $$$k$$$ символов, каждый из которых — это либо строчная латинская буква или символ подчеркивания. Все шаблоны попарно различны.

В каждой из следующих $$$m$$$ строк записана строка — $$$k$$$ строчных латинских букв, и целое число $$$mt$$$ ($$$1 \le mt \le n$$$) — номер первого шаблона, под который должна подходить соответствующая строка.

Выходные данные

Выведите «NO», если невозможно переупорядочить шаблоны так, чтобы первый шаблон, под который подходит $$$j$$$-я строка, был $$$p[mt_j]$$$.

В противном случае выведите «YES» в первой строке. Во второй строке выведите $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — порядок шаблонов. Если существует несколько ответов, выведите любой из них.

Примеры
Входные данные
5 3 4
_b_d
__b_
aaaa
ab__
_bcd
abcd 4
abba 2
dbcd 5
Выходные данные
YES
3 2 4 5 1
Входные данные
1 1 3
__c
cba 1
Выходные данные
NO
Входные данные
2 2 2
a_
_b
ab 1
ab 2
Выходные данные
NO
Примечание

Порядок шаблонов в первом примере после переупорядочивания:

  • aaaa
  • __b_
  • ab__
  • _bcd
  • _b_d

Тогда первая строка подходит под шаблоны ab__, _bcd, _b_d в таком порядке, первый из них равен ab__, который действительно $$$p[4]$$$. Вторая строка подходит под шаблоны __b_ и ab__, первый из них __b_, который равен $$$p[2]$$$. Последняя строка подходит под шаблоны _bcd и _b_d, первый из них _bcd, который равен $$$p[5]$$$.

Ответ на этот тест не единственный, другие корректные порядки существуют.

Во втором примере cba не подходит под шаблон __c, а значит, корректного порядка не существует.

В третьем примере в порядке (a_, _b) получается, что первый шаблон под который подходят обе строки — это $$$1$$$, а в порядке (_b, a_) получается, что первый шаблон под который подходят обе строки — это $$$2$$$. Значит, не существует такого порядка, что ответ равен $$$1$$$ и $$$2$$$.