PROBLEM STATEMENT.

You are given a string S. Your task is to find a longest substring of S, which is also the prefix of s and occurs atleast k times in s.

INPUT

The input will contain 3 lines. First line will have an integer n, representing the size of input string.
The second line will contain a string S of length n. The third line will have k, as described in problem statement.

OUTPUT

Output will consist of two lines. The first line will be length of longest such substring.
Print this substring in the second line.

CONSTRAINTS

• 1 = n = 1000000
• 1 = k = n
• All characters in S will be lower-case ('a'-'z') and upper-case('A'-'Z') latin characters, without any spaces.

EXAMPLE

Input

14
abacabacabacab
3

Output

6
abacab

Explanation

String "abacab" is a prefix of s and occurs 3 times in s i.e s[1,6], s[5,10], and s[9,14].