Приближается новый учебный год, и декану нужно составить расписание занятий для первого курса. Всего в расписании должно быть n пар. За последние годы было сделано интересное наблюдение: студенты прогуливают все пары с чётными номерами и посещают все пары с нечётными номерами (пары нумеруются начиная с единицы). Конечно же, декан хочет, чтобы студенты посетили как можно больше важных пар, поэтому он постарается поставить более важные пары на места с нечётными номерами, а менее важные — на места с чётными номерами. Но так как факультет у нас математико-механический, то к оценке расписания нужно подойти максимально формально.

В расписание первому курсу можно поставить любой из 26 преподаваемых на факультете предметов. Обозначим их строчными латинскими буквами от a до z. Назовём важностью предмета его позицию в английском алфавите, таким образом предмет a будет иметь важность 1, а предмет z — важность 26. Качеством расписания занятий назовём сумму важностей предметов в нём, причём предметы на местах с нечётными номерами входят в эту сумму со знаком плюс, а предметы с чётными номерами — со знаком минус.

К сожалению, административные препятствия ограничивают свободу декана. Во-первых, в расписании должно быть хотя бы k различных предметов, поэтому декану могут не дать поставить на все нечётные места пары по матанализу, а на все чётные — пары по философии. Во-вторых, на некоторых местах должны стоять определённые предметы. Помогите декану составить самое качественное расписание с учётом этих ограничений!

В первой строке дана строчка длины n (1 ≤ n ≤ 10⁵) из строчных латинских букв и знаков вопроса, задающая предметы, которые уже стоят в расписании. Буквы обозначают эти предметы, а знаки вопроса — свободные пары. Во второй строке дано целое число k (1 ≤ k ≤ 26) — минимальное количество различных предметов в расписании.

Если невозможно заменить все знаки вопроса на строчные латинские буквы так, чтобы в строчке было хотя бы k различных букв, выведите «-1» (без кавычек). Иначе выведите любой из способов замены, максимизирующих качество расписания занятий, задаваемого полученной строчкой.

В первом примере декан может сделать любое расписание из двух пар (даже одинаковых). Но качество расписания «za» равно 26 − 1 = 25, и это самый качественный вариант.

Во втором примере нельзя составить расписание из двух пар с тремя различными предметами.

В третьем примере у декана нет свободы выбора. И хоть расписание получилось плохим (1 − 26 + 1 = −24), ничего лучше предложить нельзя.

В четвёртом примере единственный возможный вариант не содержит трёх различных предметов.