Remote Training on Programming

Once professor X^{Insert a name here} has given an assignment to R students: they were to write a program for for addition of long R-digit positive integers. Unfortunately, he has forgotten to inform the student about the base of number system. The first student was responsible for development of addition routine for the first digit of number, the second student - for the second digit, etc. After that each student has chosen his/her own base of a number system P_i for that digit. If decimal digits were not sufficient to write digits in that number system then capital Latin letters (A, B, C, ..., Z) were used.

As soon as the professor knew the bases of number systems for each digit, he prepared a set of tests. Each test consists of a pair of long R-digit numbers. The task of calculating the sum of these numbers is left to you. Digit number i in the representation of the sum must be written in the number system with base P.

Write a program , which will be calculate the sum of two numbers, given a value of R, two long numbers and a list of a number system bases. It is guaranteed that the result will fit in R digits without the risk of overflow.

Let R=3 and the bases of the number system be P₁=12, be P₂=2, be P₃=4. Then the following equations are correct: 802+001=803, 803+001=810, 813+001=900, 813+012=911, 813+213=B12

Input

The first line of the input file consists of a single integer value R - the number of digits in the numbers being adding (and in the result).

The second and the third lines contains the numbers being added , N₁ and N₂ respectively. Each of these numbers is a string of R characters exactly.

The following one or more lines contain R positive integers denoting the bases of number systems for each of the R digits enumerated left to right. The numbers are delimited by whitespace and/or line feed characters.

Output

The output file must contain a singe line having R characters exactly - the number (N₁+N₂) written according to the same rules as for the given numbers.

Limitations

1<=R<=1000

2<=P_i<=36 (1<=i<=R)

Samples

3 
813
012
10 2 4

911

4
0011
00A0
2 2 11 2

0101

2
AZ
01
12 36

B0