Add and Minimize#12

Add and Minimize

1 second
256 megabytes
Medium

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 .

Input

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

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

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].

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.