Вам даны $$$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
Порядок шаблонов в первом примере после переупорядочивания:
Тогда первая строка подходит под шаблоны 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$$$.
