공장에서 빨간색과 파란색, 두 종류의 색종이를 만들고 있습니다.

각 빨간색 종이에는 문자열 $S$가 적혀 있습니다. 이 종이는 $|S|$개의 단위 정사각형이 한 줄로 이어져 있으며, 왼쪽에서 $i$번째 정사각형에는 $S_i$가 적혀 있습니다.

각 파란색 종이에는 문자열 $T$가 적혀 있습니다. 이 종이는 $|T|$개의 단위 정사각형이 한 줄로 이어져 있으며, 왼쪽에서 $i$번째 정사각형에는 $T_i$가 적혀 있습니다.

당신은 빨간색 종이와 파란색 종이를 사용하여 이중 색종이(double-colored paper)라는 새로운 종류의 종이를 만들 계획입니다. 이를 위해 빨간색 종이에서 양의 정수 길이를 가진 연속된 부분을 잘라내고, 파란색 종이에서도 마찬가지로 연속된 부분을 잘라냅니다. 그 후, 빨간색 조각의 끝과 파란색 조각의 시작 부분을 이어 붙입니다.

예를 들어, $S$가 abcde이고 $T$가 fghij라고 가정해 봅시다. 당신은 bcdfg 또는 abcij와 같은 문자열이 적힌 이중 색종이를 만들 수 있습니다. 하지만 acdghij나 fghij와 같은 문자열이 적힌 이중 색종이는 만들 수 없습니다. (여기서 밑줄 친 문자열은 빨간색 조각을, 나머지는 파란색 조각을 나타냅니다.) 두 이중 색종이는 적힌 빨간색 문자열과 파란색 문자열이 각각 같으면 같은 것으로 간주합니다.

만들 수 있는 모든 서로 다른 이중 색종이 중에서, 적힌 문자열이 사전순으로 $K$번째로 작은 것을 찾고자 합니다. 참고로, 적힌 문자열은 같지만 빨간색 종이의 길이가 다른 종이들이 존재할 수 있는데, 이 경우 순서는 임의로 정해도 됩니다.

입력

첫 번째 줄에는 문자열 $S$가 주어집니다. 두 번째 줄에는 문자열 $T$가 주어집니다. 세 번째 줄에는 정수 $K$가 주어집니다.

• $1 \le |S| \le 75\,000$
• $1 \le |T| \le 75\,000$
• $S$와 $T$는 소문자 영어 알파벳으로 구성됩니다.
• $1 \le K \le 8 \cdot 10^{18}$

출력

만들 수 있는 모든 이중 색종이의 총 개수가 $K$보다 작으면 $-1$을 출력합니다. 그렇지 않으면, 만들 수 있는 모든 이중 색종이 중 사전순으로 $K$번째로 작은 문자열을 출력합니다.

예제

입력 1

tww
wtw
21

출력 1

wwtw