给你 $$$n$$$ 模式 $$$p_1, p_2, \dots, p_n$$$ 和 $$$m$$$ 字符串 $$$s_1, s_2, \dots, s_m$$$。每个模式 $$$p_i$$$ 由 $$$k$$$ 字符组成,这些字符可以是小写拉丁字母或通配符(用下划线表示)。所有模式都是成对不同的。每个字符串 $$$s_j$$$ 由 $$$k$$$ 小写拉丁字母组成。
如果对于从 $$$1$$$ 到 $$$k$$$ 的每个 $$$i$$$,$$$b_i$$$ 是通配符或 $$$b_i=a_i$$$,则字符串 $$$a$$$ 与模式 $$$b$$$ 匹配。
系统会要求您重新排列模式,使 $$$j$$$ 字符串匹配的第一个模式是 $$$p[mt_j]$$$。您可以保持模式的顺序不变。
你能进行这样的重新排列吗?如果可以的话,请打印任何有效的订单。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n, m \le 10^5$$$, $$$1 \le k \le 4$$$) — 模式数量、字符串数量以及每个模式和字符串的长度。
接下来的 $$$n$$$ 行都包含一个模式 — $$$k$$$ 个字符,这些字符可以是小写拉丁字母或下划线。所有模式都是成对不同的。
接下来的 $$$m$$$ 行包含一个字符串 - $$$k$$$ 小写拉丁字母和一个整数 $$$mt$$$ ($$$1 \le mt \le n$$$) - 相应字符串应匹配的第一个模式的索引。
输出
如果无法重新排列模式以使第 $$$j$$$ 字符串匹配的第一个模式是 $$$p[mt_j]$$$,则打印“NO”。
否则,在第一行打印“YES”。第二行应包含从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数 - 模式的顺序。如果有多个答案,请打印其中任何一个。
示例
输入 #1
5 3 4 _b_d __b_ aaaa ab__ _bcd abcd 4 abba 2 dbcd 5
输出 #1
YES 3 2 4 5 1
输入 #2
1 1 3 __c cba 1
输出 #2
NO
输入 #3
2 2 2 a_ _b ab 1 ab 2
输出 #3
NO
注意
第一个示例中重新排列后的模式顺序如下:
- 啊啊啊
- __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$$$ 的顺序。