A - Lost Key

Time limit: 2 s
Memory limit: 2048 MiB
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$.

Sample test(s)

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