You are given an array a_1,a_2,\dots,a_n and a string s_1,s_2,\dots,s_n.
You can change the order of elements in the array as you like.
Your task is to make the string s_1+a_1,s_2+a_2,\dots,s_n+a_n lexicographically minimal.
s_i+a_i means that s_i has been replaced by the next letter in the alphabet exactly a_i times. The letter "z" is replaced by "a".
A string is lexicographically smaller than a string if in the first position where and differ, the character at position is smaller than the character at position .
The first line contains the number (1\le n\le 10^5) — the size of the array and the string.
The second line contains integers a_1,\dots,a_n (1\le a_i\le 10^9) — the elements of the array .
The third line contains the string with characters. It is guaranteed that all characters in the string are lowercase letters of the English alphabet.
Output the lexicographically minimal string s_1+a_1,\dots,s_n+a_n after changing the order of the elements in .
Example
Example 1
In the first test, there are a total of ways to change the order of the array elements:
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{'}]="";
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{'}]="";
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{'}]="";
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{'}]="";
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{'}]="";
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{'}]="".
The lexicographically minimal of these strings is "".
In the second test, the optimal order of elements is a=[26,1,2,4,6].
In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Please note that the evaluation is still being tested.
(5 points): n\le 5, a_i\le 1000;
(20 points): n\le 3000;
(75 points): without additional constraints.