All Tracks Algorithms String Algorithms Problem

Naughty Vineeth

Implementation, String Algorithms, Very-Easy, Very-Easy


As we know, Vineeth is a very naughty nerd. One day he had to delete his browser history. As there was plenty of links to delete, He came up with an idea of creating a special String that had the capability of deleting the required links and he named such String as "Naughty String".

As there were totally n links in his browser and he needs to delete some of them. All the required links should only match the pattern of Naughty String.

The only special character Vineeth knows is a question mark '?' which matches any single character. All other characters in the Naughty String match themselves only.

Formally, a Naughty String matches a link if and only if they have equal lengths and all characters in the corresponding positions are equal except when the character in the Naughty String is '?', in which case the corresponding link character does not matter.

For example, the link pattern "a?ba?":

matches links "aabaa", "abba.", "a.ba9" and ""
does not match links "aaba", "abaab", "aabaaa" and "aabaa."
Help Vineeth find a Naughty String or report if there is no such String.


The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 100) — the total number of links and the number of links to be deleted.

The following n lines contain links, single link per line. All links are non-empty strings containing only lowercase English letters, digits and dots ('.'). The length of each link doesnt exceed 100. It is guaranteed that all links are distinct.

The last line of the input contains m distinct integer numbers in ascending order a1, a2, ..., am (1 ≤ ai ≤ n) — indices of links to be deleted. All links are indexed from 1 to n in order of their appearance in the input.


If the required Naughty String exists, print "Yes" in the first line of the output. The second line should contain the required Naughty String.

If the required Naughty String doesnt exist, print the only line containing "No"

The created Naughty String must contain minimum number of '?' (Special Character)

2 2
1 2
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications