A new academic year approaches, and the dean must make a schedule of classes for first-year students. There must be n classes in the schedule. The dean should take into account the following interesting observation made in recent years: students skip all classes with even numbers and attend all classes with odd numbers (the classes are numbered from 1). Of course the dean wants students to attend as many important classes as possible, so he tries to assign subjects that are more important to places with odd numbers and subjects that are less important to places with even numbers. The method of estimating the quality of the schedule at the Department of Mathematics and Mechanics must be as formal as possible.

The first-year schedule may contain any of 26 subjects taught at the department. We denote them by English letters from a to z. The importance of a subject corresponds to its position in the English alphabet. Thus, subject a has importance 1, and subject z has importance 26. The quality of a schedule is the sum of importances of subjects in it, where subjects on odd places are counted with a plus sign, and subjects on even places are counted with a minus sign.

Unfortunately, a shedule has some restrictions due to administrative reasons. First, the schedule must contain at least k different subjects, so the dean cannot occupy all odd places with mathematical analysis and all even places with philosophy. Second, certain subjects must be assigned to certain places. Help the dean to make a schedule of maximum quality under these restrictions.

The first line contains a string of length n (1 ≤ n ≤ 10⁵) consisting of lowercase English letters and question marks. The string specifies the subjects that are already in the schedule. The letters denote these subjects, and the question marks stand for vacant places. In the second line you are given an integer k (1 ≤ k ≤ 26), which is the minimum number of different subjects in the schedule.

If it is impossible to replace all question marks by lowercase English letters so that the string would contain at least k different letters, output “-1” (without quotation marks). Otherwise, output any of the resulting strings that maximizes the quality of the schedule given by the string.

In the first sample the dean can make any schedule with two subjects (even identical), but the quality of the schedule “za” is 26 − 1 = 25, and this is the maximum possible value of the quality.

In the second sample it is impossible to make a schedule consisting of two classes with three different subjects.

In the third sample the dean has only one variant. Though the schedule is bad (1 − 26 + 1 = −24), nothing better can be proposed.

In the fourth sample the only possible variant doesn’t contain three different subjects.