In problems on strings one often has to find a string with some particular properties. The problem authors were reluctant to waste time on thinking of a name for some string so they called it good. A string is good if it doesn't have palindrome substrings longer than or equal to d.

You are given string s, consisting only of lowercase English letters. Find a good string t with length |s|, consisting of lowercase English letters, which is lexicographically larger than s. Of all such strings string t must be lexicographically minimum.

We will call a non-empty string s[a...b]=s_as_a+1... s_b (1≤a≤b≤|s|) a substring of string s=s₁s₂... s_|s|.

A non-empty string s=s₁s₂... s_n is called a palindrome if for all i from 1 to n the following fulfills: s_i=s_n-i+1. In other words, palindrome read the same in both directions.

String x=x₁x₂... x_|x| is lexicographically larger than string y=y₁y₂... y_|y|, if either |x|>|y| and x₁=y₁,x₂=y₂,... ,x_|y|=y_|y|, or there exists such number r (r<|x|,r<|y|), that x₁=y₁,x₂=y₂,... ,x_r=y_r and x_r+1>y_r+1. Characters in such strings are compared like their ASCII codes.