Redoan is very fond of strings. He wants to go on a spree of solving string problems. His own teammate Nafis is very jealous of him. He wants to stop the streak of "Accepted" in Redoan's string problem solving. So he decides to take help from Pizon. Pizon thought for whole night and then an idea came to his mind. He went to Redoan and gave him the following problem. There are N strings given to Redoan. They have at most M length each. Redoan has to make another string joining K distinct strings from the given list. If there are not K unique strings available then he can join as many as possible. Of course those also have to be unique. Nafis is still not convinced. He wants to make this problem harder. So he added another constraint. Redoan must pick lexicographically smaller strings first.

Input

First line contains N. N strings follow. Then K is given. 1 <= N <= 1000000, K <= N, M <= 4. Each of the number mentioned earlier will be positive.