Add and Minimize

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 $a$ 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 $A$ is lexicographically smaller than a string $B$ if in the first position where $A$ and $B$ differ, the character at position $A$ is smaller than the character at position $B$.

Input

The first line contains the number $n$ ($1\le n\le 10^5$) — the size of the array and the string.

The second line contains $n$ integers $a_1,\dots ,a_n$ ($1\le a_i\le 10^9$) — the elements of the array $a$.

The third line contains the string $s$ with $n$ characters. It is guaranteed that all characters in the string are lowercase letters of the English alphabet.

Output

Output the lexicographically minimal string $s_1+a_1,\dots ,s_n+a_n$ after changing the order of the elements in $a$.

Examples

Note

In the first test, there are a total of $6$ 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{’}]=$"$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$".

The lexicographically minimal of these strings is "$bdf$".

In the second test, the optimal order of elements is $a=[26,1,2,4,6]$.

Scoring

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.

1. (5 points): $n\le 5$, $a_i\le 1000$;

2. (20 points): $n\le 3000$;

3. (75 points): without additional constraints.