Додай і мінімізуй

Вам дано масив $a_1,a_2,\dots ,a_n$ та рядок $s_1,s_2,\dots ,s_n$.

Ви можете змінити порядок елементів масиву $a$ як завгодно.

Ваша задача — зробити рядок $s_1+a_1,s_2+a_2,\dots ,s_n+a_n$ лексикографічно мінімальним.

$s_i+a_i$ означає, що $s_i$ було замінено на наступну букву за алфавітом рівно $a_i$ раз. Буква «z» заміняється на «a».

Рядок $A$ лексикографічно менший за рядок $B$, якщо в першій позиції, де $A$ та $B$ відрізняються, символ на позиції $A$ менший від символу на позиції $B$.

Вхідні дані

Перший рядок містить число $n$ ($1\le n\le 10^5$) — розмір масиву та рядка.

Другий рядок містить $n$ цілих чисел $a_1,\dots ,a_n$ ($1\le a_i\le 10^9$) — елементи масиву $a$.

Третій рядок містить рядок $s$ з $n$ символів. Гарантується, що в рядку всі символи — маленькі букви англійського алфавіту.

Вихідні дані

Вивести лексикографічно мінімальний рядок $s_1+a_1,\dots ,s_n+a_n$ після змінення порядку елементів $a$.

Приклади

Примітка

У першому тесті всього є $6$ способів змінити порядок елементів масиву:

• $a=[1,2,3]$, $s=[\text{’}a\text{’}+1,\text{’}b\text{’}+2,\text{’}c\text{’}+3]=[\text{’}b\text{’},\text{’}d\text{’},\text{’}f\text{’}]=$"$bdf$";

• $a=[1,3,2]$, $s=[\text{’}a\text{’}+1,\text{’}b\text{’}+3,\text{’}c\text{’}+2]=[\text{’}b\text{’},\text{’}e\text{’},\text{’}e\text{’}]=$"$bee$";

• $a=[2,1,3]$, $s=[\text{’}a\text{’}+2,\text{’}b\text{’}+1,\text{’}c\text{’}+3]=[\text{’}c\text{’},\text{’}c\text{’},\text{’}f\text{’}]=$"$ccf$";

• $a=[2,3,1]$, $s=[\text{’}a\text{’}+2,\text{’}b\text{’}+3,\text{’}c\text{’}+1]=[\text{’}c\text{’},\text{’}e\text{’},\text{’}d\text{’}]=$"$ced$";

• $a=[3,1,2]$, $s=[\text{’}a\text{’}+3,\text{’}b\text{’}+1,\text{’}c\text{’}+2]=[\text{’}d\text{’},\text{’}c\text{’},\text{’}e\text{’}]=$"$dce$";

• $a=[3,2,1]$, $s=[\text{’}a\text{’}+3,\text{’}b\text{’}+2,\text{’}c\text{’}+1]=[\text{’}d\text{’},\text{’}d\text{’},\text{’}d\text{’}]=$"$ddd$".

Лексикографічно мінімальний з цих рядків — це "$bdf$".

У другому тесті оптимальний порядок елементів це $a=[26,1,2,4,6]$.

Оцінювання

У цій задачі існують умовні блоки. Якщо ваше рішення буде працювати правильно для певних обмежень, то воно отримуватиме певну кількість балів. Зверніть увагу, що оцінювання й досі потестове.

1. ($5$ балів): $n\le 5$, $a_i\le 1000$;

2. ($20$ балів): $n\le 3000$;

3. ($75$ балів): без додаткових обмежень.