Zero Run Pattern

Time limit2sMemory limit128 MB

Summary

Given two binary strings repeated in a growing pattern, find the first position within the first 10^16 characters where C consecutive zeros occur.

Level: Hard8 of 10
Topics: String, Binary search, Math, Simulation
Solved: No attempts yet

Problem

Two binary strings S1 and S2 are given. For a positive integer N, define S(N) as the string made by concatenating 1,000,000 copies of S1, followed by N copies of S2.

The infinite string S is formed by concatenating S(1), S(2), S(3), ... in order. Let T be the first 10^16 characters of S.

Find the first position in T where a substring of length C consisting only of 0 appears. Positions are 0-based.

Input

The first line contains S1, and the second line contains S2. Each string consists only of 0 and 1, and each has length at most 50.

The third line contains the positive integer C, where C <= 10^16.

Output

Print the answer on one line. If no such substring exists, print -1.

Examples5

Example 1
Input
```
111010100001010
010000001000
3
```
Expected output
```
7
```
Example 2
Input
```
1101010010
0001000
3
```
Expected output
```
9999999
```
Example 3
Input
```
1101010010
0001000
5
```
Expected output
```
20000011
```
Example 4
Input
```
10101010
101010101010
9876543219876
```
Expected output
```
-1
```

Example 5

Input

11111111111111111111111111
0
9876543219876

Expected output

-1