Given a string $S$ and a binary string $P$ of the same length as $S$, construct a non-empty string $T$ (which must consist only of lowercase English letters) that satisfies the following conditions:
- For $1 \leq i \leq |S| - |T| + 1$, $P[i] = 1$ if and only if $T$ occurs as a substring in $S$ starting exactly at index $i$.
- For $|S| - |T| + 1 < i \leq |S|$, $P[i] = 0$.
If such a string $T$ exists, output any valid $T$ with a length not exceeding $10^6+1$ (such a $T$ is guaranteed to exist if a solution is possible); otherwise, output -1.
Input
The first line contains a string $S$ consisting of lowercase English letters ($1 \leq |S| \leq 10^6$).
The second line contains a binary string $P$ of the same length as $S$.
Output
Output a string $T$ or -1. If there are multiple possible strings $T$, you may output any one of them.
$T$ must consist only of lowercase English letters.
Examples
Input 1
baaababaab 0001010000
Output 1
aba
Input 2
zqjzqj 000000
Output 2
test
Input 3
zqjzqj 100001
Output 3
-1
Note
For the first example, $T$ can only be aba.
For the second example, any $T$ that is not a substring of $S$ is valid.
For the third example, no valid $T$ exists, so the answer is -1.
Subtasks
For $30\%$ of the test cases: $|S| \leq 10$, and $S$ contains only 'a' or 'b'.
For $50\%$ of the test cases: $|S| \leq 100$.
For $70\%$ of the test cases: $|S| \leq 1000$.
For $100\%$ of the test cases: $|S| \leq 10^6$.