A - Lost Key

Languages: C, C++, Java, Python, ... (details)

Juan designed a very unorthodox encryption algorithm. This works as follows:

Given a string $A = a_0a_1a_2 \ldots a_{n-1}$, and a key $K = k_0k_1k_2\ldots k_{m - 1}$, the algorithm encrypts the string $A$, in a resultant string $B = b_0b_1b_2 \ldots b_{n-1}$, where $b_i = a_i + k_{i \mod m}$. We define the sum of two characters $x'$ and $y'$ as the letter that is at position $z'$ in the alphabet, where $z'$ is the result of summing the number of the position of the letter $x'$ in the alphabet plus the number of the position of the letter $y'$ in the alphabet modulo $26$ (cyclically). All positions in the alphabet are indexed starting from $0$.

Example: The encryption of the string $A$ = caribe with the key $K$ = icpc will return the string $B$ = kcgkjg, through  the following steps:

1. Letter k is at  position  $10 = (\, 2 \, + \, 8\, ) _{\mod 26}$,  c  is at position  $2$  and  i  is at position  $8$.
2. Letter c is at position    $2\,= (\, 0 \, + \, 2\, )_{ \mod 26}$,  a  is at position  $0$  and  c  is at position  $2$.
3. Letter g is at position    $6\, = ( 17 + 15 )_{\mod 26}$,  is at position $17$ and  p  is at position  $15$.
4. Letter is at position   $10 = (\, 8 \, + \, 2\, )_{\mod 26}$,  i  is at position  $8$  and  c  is at position  $2$.
5. Letter  j is at position    $9 = (\, 1\, + \, 8\, )_{\mod 26}$,  is at position  $1$  and  is at position  $8$.
6. Letter g is at position   $6 = (\, 4 \, + \, 2\, )_{\mod 26}$,  is at position  $4$ and  is at position  $2$.

Juan started encrypting a text yesterday and today he needs to continue. However, he has lost $K$. Help Juan to find the key, so he can continue working. Juan will give you a string, $A$, and its corresponding encryption, $B$.

Input

First line contains two strings, composed by lowercase letters, separated by a space, $A$ and $B$ $(|A| = |B|, 1 \leq |A| \leq 100)$. Second line contains $m (1 \leq m \leq 4, m \leq |A| )$, the size of the lost key.}

Output

Print the key, a string of lowercase letters, if you could find it, or -1, if it is impossible to get $B$ from $A$ with a key of size $m$.

Input
caribe kcgkjg 4
Output
icpc
Input
latin lbfop 3
Output
-1
Input
zombie zamniq 2
Output
am