Задача . D. Задача на доске

Поликарп написал на доске некоторую строку \(s\) из строчных букв латинского алфавита ('a'-'z'). Эта строка вам известна и задана во входных данных.

После этого он стёр какие-то буквы из строки \(s\), а оставшиеся буквы он переписал в произвольном порядке. В результате он получил некоторую новую строку \(t\). Её вам и предстоит найти по некоторой дополнительной информации.

Предположим, что длина строки \(t\) равна \(m\), а символы пронумерованы слева направо от \(1\) до \(m\). В таком случае вам задана последовательность из \(m\) целых чисел: \(b_1, b_2, \ldots, b_m\), где \(b_i\) равно сумме расстояний \(|i-j|\) от индекса \(i\) до всех таких индексов \(j\), что \(t_j > t_i\) (считайте, что 'a'<'b'<...<'z'). Иными словами, для вычисления \(b_i\) Поликарп находит все такие индексы \(j\), что в индексе \(j\) находится буква, которая стоит позже в алфавите чем \(t_i\), и суммирует все значения \(|i-j|\).

Например, если \(t\)=«abzb», то:

• так как \(t_1\)='a', то все остальные индексы содержат буквы, которые позже в алфавите, то есть: \(b_1=|1-2|+|1-3|+|1-4|=1+2+3=6\);
• так как \(t_2\)='b', то только индекс \(j=3\) содержит букву, которая позже в алфавите, то есть: \(b_2=|2-3|=1\);
• так как \(t_3\)='z', то индексов \(j\), что \(t_j>t_i\) не существует: \(b_3=0\);
• так как \(t_4\)='b', то только индекс \(j=3\) содержит букву, которая позже в алфавите, то есть: \(b_4=|4-3|=1\).

Таким образом, если \(t\)=«abzb», то \(b=[6,1,0,1]\).

По заданной строке \(s\) и массиву \(b\) найдите любую возможную строку \(t\), для которой выполняются следующие два требования одновременно:

• \(t\) получается из \(s\) путём стирания некоторых букв (возможно, нуля) и потом записи оставшихся в произвольном порядке;
• по строке \(t\) получается заданный во входных данных массив \(b\), если его построить по правилам, которые описаны выше.