Додай і мінімізуй
ліміт часу на тест
1 second
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Вам дано масив $$$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$$$.

Система оцінки

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

1. ($$$5$$$ балів): $$$n\le 5$$$, $$$a_i\le 1000$$$;
2. ($$$20$$$ балів): $$$n\le 3000$$$;
3. ($$$75$$$ балів): без додаткових обмежень.

Приклади

Вхідні дані

    31 2 3abc

Вихідні дані

    bdf

Вхідні дані

    52 26 4 6 1abzxy

Вихідні дані

    acbbe

Пояснення

У першому тесті всього є $$$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]$$$.