Double subline

Given a string S of length n and a number k.

Your task is to find a substring of length k within the string S that appears at least twice. If no such substring exists, indicate this.

Input

The first line of the input contains the string S, which has a length n ranging from 1 to 100000 characters. The second line contains an integer k (1 ≤ k ≤ n). The string consists solely of lowercase Latin letters.

Output

If there is no substring of length k that appears at least twice, print the word NONE on the first line of the output. Otherwise, print any one of such substrings on the first line of the output.

Examples