COCI '16 Contest 2 #2 Tavan

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

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 were. After seeing the words written down in the notebook, his grandma realized that the word they're looking for is the X^\text{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.

Input Specification

The first line of input contains the integers N, M, K and X (1 \leq N \leq 500, 1 \leq M \leq N, 1 \leq K \leq 26, 1 \leq X \leq 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^\text{th} of these words consisting of letters that could replace the i^\text{th} illegible letter.

Output Specification

The first line of output must contain the X^\text{th} word in alphabetical order.


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.

Sample Input 1

9 2 3 7

Sample Output 1


Explanation for Sample Output 1

The possible words, in alphabetical order, are: pololjeni, pololjeui, pololjezi, poooljeni, poooljeui, poooljezi, posoljeni, posoljeui, posoljezi.

Sample Input 2

4 1 2 2

Sample Output 2



There are no comments at the moment.