Crypto Cup 1.0
A. Bank
time limit per test
2 seconds
memory limit per test
64 megabytes
input
stdin
output
stdout

You are given an encrypted number, encrypted using a certain algorithm.Decrypt it !

Input

The first line contains keys, n, e (1 ≤ n, e ≤ 106).

Next line contains encrypted number

Output

Print the original number.

Examples
Input
2461 2007
2097
Output
2175
Input
65783 58199
53581
Output
12356
Input
409763 128561
82222
Output
311454
B. :-P
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it !

Input

The first line of input contains a string s, which each of it's characters is a lower case English letter. (1 ≤ |s| ≤ 105)

The second line contains single integer p. (1 ≤ p ≤ |s|)

Output

Print the original string.

Examples
Input
crhhzae
3
Output
charzeh
Input
yeofuis
4
Output
yousefi
Input
mtm
2
Output
mmt
C. Pgkpxumgs
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm.Decrypt it !

Input

The first and single line of input contains a string s, which each of it's characters is a lower case English letter. (1 ≤ |s| ≤ 105)

Output

Print the original string.

Examples
Input
cjjazdk
Output
charzeh
Input
ymgychp
Output
yousefi
Input
myr
Output
mmt
D. 13lk
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm.Decrypt it !

Input

The first and single line of input contains a string s, which each of it's characters is a digit or ,  or Z or O. (1 ≤ |s| ≤ 105)

Output

Print the original string.

Examples
Input
Z,1,2,3,2,1,2,1,1,4,2,4,1,1,3,2,1,2,4,1,1,2,2,2,1,1,1,1,2,1,1,3
Output
charzeh
Input
Z,1,1,1,2,2,1,1,2,1,4,1,3,1,1,1,1,1,3,2,2,1,2,2,1,1,1,1,2,2,2,2,2,1,1,2,1
Output
Yousefi
Input
Z,1,2,1,2,1,1,1,2,1,2,1,1,1,3,1,1,4,2,6,2,3,1
Output
mmt01
E. Peace of AmericanWedding
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm.Decrypt it !

Input

The first and single line of input contains a string s, which each of it's characters is U or F or space. (1 ≤ |s| ≤ 105)

Output

Print the original string.

Examples
Input
UFUF FFFF FU FUF UUFF F FFFF
Output
CHARZEH
Input
UFUU UUU FFU FFF F FFUF FF
Output
YOUSEFI
Input
UU UU U UUUUU FUUUU
Output
MMT01
F. 2715
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm.Decrypt it !

Input

The first and single line of input contains a string s, which each of it's characters is a lower case English letter. (1 ≤ |s| ≤ 105)

Output

Print the original string.

Examples
Input
hhcnjbff
Output
charzeh
Input
dnadddaaj
Output
yousefi
Input
cnli
Output
mmt
Input
boiah
Output
easy
Input
chmijdmnh
Output
problem
G. uehSlff
time limit per test
2 seconds
memory limit per test
64 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it !

This problem is a little bit different from the other problems.This problem has 7 test cases.You can see the answer to the first two test cases.

You are given the inputs for all test cases :

Case #1 : eczhrah

Case #2 : ytmomeufsi

(The original string for each of the following 5 test cases, is an English sentence (or a name) witch has a meaning. like : thebigbangtheory or pleaseshutup)

Case #3 : yvuoedloreoic

Case #4 : lbciutrps

Case #5 : asadiepriemrvheit

Case #6 : ajsiltlltfutusehef

Case #7 : eresordngizaeoumsab

Input

For all test cases, you're given a single string.

Output

Print the original string.

Examples
Input
eczhrah
Output
charzeh
Input
ytmomeufsi
Output
yousefimmt
H. Peace of AmericaReunion
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it !

Input

The first line of input contains 26 integers a1, ..., a26 separated by space (1 ≤ ai ≤ 105).

Next lines, each line contains an integer between 1 and 105 inclusive.

Output

Print a single string in a single line.

Examples
Input
1 0 1 0 1 0 0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
3
1
6
2
7
4
5
Output
charzeh
Input
0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0
5
6
7
2
4
3
1
Output
yousefi
Input
0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0
1
2
3
Output
mmt
I. Peace of AmericanPie
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it !

Input

The first and only line of input contains a string s,each character of s is either 0 or 1 . (8 ≤ |s| ≤ 8 × 104)

Output

Print the original string.

Examples
Input
01100011011010000110000101110010011110100110010101101000
Output
charzeh
Input
01111001011011110111010101110011011001010110011001101001
Output
yousefi
Input
0100110101001101010101000011000000110001
Output
MMT01
J. Common
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it !

Input

The first and single line of input contains a string s, which each of it's characters is a lower case English letter. (1 ≤ |s| ≤ 105)

Output

Print the original string.

Examples
Input
wbpctfb
Output
charzeh
Input
ghnxfuv
Output
yousefi
Input
jjy
Output
mmt
Input
lvevavsvcz
Output
bikinigirl
Input
mkojrpcf
Output
djvmware
Input
qcvhcvyginfnf
Output
priorityqueue
Input
djfa
Output
xmen
K. Crap
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it !

It's guaranteed that the original string is made of lower case English letters.

Input

The first line of input contains integer n, the size of the encrypted sequence. (1 ≤ n ≤ 105).

The second line contains n integers between 0 and 10^9+6 inclusive, speared by space.

Output

Print the original string.

Examples
Input
7
99 3173 98460 3052374 94623716 933335283 933393681
Output
charzeh
Input
7
121 3862 119839 3715124 115168945 570237376 677358642
Output
yousefi
Input
3
109 3488 108244
Output
mmt
L. Key
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm.Decrypt it !

Each character of the encrypted string has ASCII code between 0 and 255 inclusive.So you're given the ASCII code of each character.It's guaranteed that the original string is made of lower case English letters.

Input

The first line of input contains integer n, the size of the encrypted string. (7 ≤ n ≤ 105).

The second line contains n integers between 0 and 255 inclusive, speared by space.

Output

Print the original string.

Examples
Input
7
17 3 8 20 25 15 7
Output
charzeh
Input
7
11 4 28 21 6 12 6
Output
yousefi
Input
8
1 14 16 3 7 7 2 6
Output
seyedmmt
M. oPlus
time limit per test
2 seconds
memory limit per test
64 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm.Decrypt it !

Each character of the encrypted string has ASCII code between 0 and 255 inclusive.So you're given the ASCII code of each character.It's guaranteed that the original string is made of lower case English letters.

Input

The first line of input contains integer n, the size of the encrypted string. (1 ≤ n ≤ 105).

The second line contains n integers between 0 and 255 inclusive, speared by space.

Output

Print the original string.

Examples
Input
7
189 182 191 172 164 187 182
Output
charzeh
Input
7
167 177 171 173 187 184 183
Output
yousefi
Input
3
179 179 170
Output
mmt
Input
11
188 183 181 183 176 183 175 171 187 172 167
Output
bikiniquery
N. tirnaoeumPt
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm.Decrypt it !

Each character of the encrypted string has ASCII code between 0 and 255 inclusive.So you're given the ASCII code of each character.It's guaranteed that the original string is made of lower case English letters.

Input

The first line of input contains integer n, the size of the encrypted string. (1 ≤ n ≤ 105).

The second line contains n integers between 0 and 255 inclusive, speared by space.

Output

Print the original string.

Examples
Input
7
8 25 0 3 7 16 25
Output
charzeh
Input
7
6 28 18 10 16 17 4
Output
yousefi
Input
3
20 20 11
Output
mmt
O. 0x
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it!

Input

The first and single line of input contains a string s, which each of it's characters is an English letter or a digit or  +  or  =  or  / . (1 ≤ |s| ≤ 105)

Output

Print the original string.

Examples
Input
Y2hhcnplaA==
Output
charzeh
Input
eW91c2VmaQ==
Output
yousefi
Input
bW10
Output
mmt
P. Proooooooooooooofer
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it!

Encryption algorithm gives a string t of length n and converts it to a pair (s, a) where s is a string of length n and a is a sequence of integers of length n - 2.

Input

The first line, contains an integer n. (3 ≤ n ≤ 105).

The second line, contains string s. The third line contains n - 2 integers a1, a2, ..., an - 2 seperated by space.

Each character of s is a lower case English letter (1 ≤ ai ≤ n and 1 ≤ i ≤ n - 2).

Output

Print t in the only line of output.

Examples
Input
7
chzhare
7 6 1 1 2
Output
charzeh
Input
7
youfise
4 4 2 4 2
Output
yousefi
Input
3
mmt
3
Output
mmt
Input
12
crpogprhitay
4 5 4 1 2 6 2 4 12 8
Output
cryptographi
Input
4
shti
3 1
Output
shit
Input
4
bull
1 2
Output
bull
Q. Peace of bzjd
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it !

Input

The first and single line of input contains a string s, which each of it's characters is a lower case English letter. (1 ≤ |s| ≤ 105)

Output

Print the original string.

Examples
Input
bgzqydg
Output
charzeh
Input
xntrdeh
Output
yousefi
Input
lls
Output
mmt
R. 6227020800
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an encrypted string, encrypted using a certain algorithm.Decrypt it !

Input

The first and single line of input contains a string s, which each of it's characters is a lower case English letter. (1 ≤ |s| ≤ 105)

Output

Print the original string.

Examples
Input
punemru
Output
charzeh
Input
lbhfrsv
Output
yousefi
Input
zzg
Output
mmt