Double substring#5465
Sign in

Double substring

2 seconds
256 megabytes
Medium

Given a string of length and a number .

Find any substring of length that appears at least twice in . If there is no such substring, indicate this.

Input

The first line contains the string , where 1 \leq n \leq 100000. The second line contains an integer (1 \leq k \leq n). The string consists only of lowercase Latin letters.

Output

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

Examples

Example 1

Loading
Loading