В задачах на строки часто требуется найти строку, обладающую какими-то особыми свойствами. В очередной раз авторам задачи было лень придумывать название для такой строки, поэтому они назвали ее хорошей. Строка называется хорошей, если в ней нет подстрок-палиндромов длины большей или равной d.

Дана строка s, состоящая только из строчных латинских букв. Найдите хорошую строку t длины |s|, состоящую из строчных латинских букв, и лексикографически большую, чем s. Из всех таких строк строка t должна быть лексикографически минимальной.

Непустую строку s[a ... b] = s_as_a + 1... s_b (1 ≤ a ≤ b ≤ |s|) будем называть подстрокой строки s = s₁s₂... s_|s|.

Непустая строка s = s₁s₂... s_n называется палиндромом, если для всех i от 1 до n выполняется s_i = s_{n - i + 1}. Другими словами, палиндромы читаются одинаково в обоих направлениях.

Строка x = x₁x₂... x_|x| лексикографически больше строки y = y₁y₂... y_|y|, если либо |x| > |y| и x₁ = y₁, x₂ = y₂, ... , x_|y| = y_|y|, либо существует такое число r (r < |x|, r < |y|), что x₁ = y₁, x₂ = y₂, ... , x_r = y_r и x_r + 1 > y_r + 1. Символы в строках сравниваются как их ASCII-коды.