시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB417523712.759%

문제

0과 1로만 이루어진 두 문자열 S1과 S2가 있다. 문자열 S(N)은 S1을 1,000,000개 연결한 다음에 S2를 N개 연결한 것이다. 길이가 무한인 문자열 S는 S(1), S(2), S(3), …을 순서대로 계속 연결한 것이다. 문자열 T는 문자열 S의 처음 1016개 문자이다.

T의 부분 문자열 중에 길이가 C이면서 0으로만 이루어진 것을 찾으려고 한다. 이러한 부분 문자열의 T에서 가장 처음 나타나는 위치를 구하는 프로그램을 작성하시오. 문자열의 위치는 0부터 시작한다.

입력

첫째 줄에 S1이 주어지고, 둘째 줄에 S2가 주어진다. S1과 S2의 길이는 최대 50이다. 셋째 줄에는 C가 주어진다. C는 1016보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 그러한 부분 문자열이 없다면 -1을 출력한다.

예제 입력 1

111010100001010
010000001000
3

예제 출력 1

7

예제 입력 2

1101010010
0001000
3

예제 출력 2

9999999

예제 입력 3

1101010010
0001000
5

예제 출력 3

20000011

예제 입력 4

10101010
101010101010
9876543219876

예제 출력 4

-1

예제 입력 5

11111111111111111111111111
0
9876543219876

예제 출력 5

-1

출처