1 \(s / 32\) \(MB / 80\) points

Little Željko has been reading his grandma’s old letters in the attic and has come across a

word of length \(N\)

. Unfortunately, he couldn’t make out what it said because of the spilled ink.

He rewrote the word on a piece of paper by replacing each of the \(M\) illegible letters with the

character ‘#’. He handed the piece of paper to his grandma and she gave him \(K\) different

candidates for each of the illegible letters. After that, Željko wrote all the possible words in a

notebook and decided to closely look at their properties in order to determine what the

original words was. After seeing the words written down in the notebook, his grandma

realized that the word they’re looking for is the \(X\)

^{th} one in alphabetical order. Željko had the

sniffles the day they learned the alphabet in school, so he’s asking you for your help with

determining the original word.

In test cases worth 30% of total points, it will hold \(M\)

= 1 and \(K\)

= 3.
In test cases worth an additional 30% of points, it will hold \(M\)

= 1.

The first line of input contains the integers \(N\)

, \(M\)

, \(K\) and \(X\) (1 ≤ \(N \le 500\), 1 ≤ \(M\) ≤ \(N\)

, 1 ≤ \(K \le 26\),

1 ≤ \(X\)

≤ 10 ^{9}{ }).
The second line of input contains the word of length \(N\) that Željko wrote on a piece of paper,

consisting of lowercase letters of the English alphabet and the character ‘#’.
Each of the following \(M\) lines contains one word of length \(K\)

, the \(i\)

\(th\) of these words consisting

of letters that could replace the \(i\)

\(th\)

illegible letter.

Number \(X\) will always be less than or equal to the total number of words that can be

constructed.

The first line of output must contain the \(X\)

\(th\)

word in alphabetical order.

생성자가 기록되지 않았습니다.

출처 COCI 2016/2017 Contest 2