Tại nhà máy của bạn, bạn đang sản xuất hai loại giấy màu, một loại màu đỏ và một loại màu xanh. Mỗi tờ giấy màu đỏ có một xâu $S$ được viết trên đó: nó được tạo thành từ $|S|$ ô vuông đơn vị xếp thành một hàng, và $S_i$ được viết trên ô vuông thứ $i$ tính từ bên trái. Mỗi tờ giấy màu xanh có một xâu $T$ được viết trên đó: nó được tạo thành từ $|T|$ ô vuông đơn vị xếp thành một hàng, và $T_i$ được viết trên ô vuông thứ $i$ tính từ bên trái.

Bạn dự định tạo ra một loại giấy mới gọi là giấy hai màu từ giấy đỏ và giấy xanh. Để làm điều đó, bạn sẽ cắt một mảnh giấy đỏ để giữ lại một phần liên tục có độ dài là số nguyên dương, sau đó làm tương tự với một mảnh giấy xanh. Sau đó, bạn sẽ dán phần cuối của mảnh giấy đỏ vào phần đầu của mảnh giấy xanh. Ví dụ, giả sử $S$ là abcde và $T$ là fghij. Bạn có thể tạo ra một tờ giấy hai màu với xâu bcdfg hoặc abcij được viết trên đó. Tuy nhiên, bạn không thể tạo ra tờ giấy hai màu với xâu acdghij hoặc fghij được viết trên đó. (Ở đây, xâu được gạch chân biểu thị mảnh giấy đỏ, và phần còn lại biểu thị mảnh giấy xanh.) Hai tờ giấy hai màu được coi là giống nhau nếu chúng có cùng xâu đỏ và cùng xâu xanh được viết trên đó.

Trong số tất cả các tờ giấy hai màu khác nhau có thể tạo ra, bạn muốn biết tờ giấy có xâu được viết trên đó nhỏ nhất theo thứ tự từ điển thứ $K$. Lưu ý rằng có thể có các tờ giấy có cùng xâu được viết trên đó nhưng với độ dài mảnh giấy đỏ khác nhau: trong trường hợp này, bạn có thể sắp xếp chúng tùy ý.

Dữ liệu vào

Dòng đầu tiên chứa xâu $S$. Dòng thứ hai chứa xâu $T$. Dòng thứ ba chứa số nguyên $K$.

• $1 \le |S| \le 75\,000$
• $1 \le |T| \le 75\,000$
• $S$ và $T$ bao gồm các chữ cái tiếng Anh viết thường
• $1 \le K \le 8 \cdot 10^{18}$

Dữ liệu ra

Nếu tổng số tờ giấy hai màu có thể tạo ra nhỏ hơn $K$, hãy in ra $-1$. Nếu không, hãy in ra xâu nhỏ nhất theo thứ tự từ điển thứ $K$ trong số tất cả các tờ giấy hai màu có thể tạo ra.

Ví dụ

Dữ liệu vào 1

tww
wtw
21

Dữ liệu ra 1

wwtw