시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB78443960.938%

문제

알파벳 소문자로 구성된 문자열 X, Y, Z가 주어진다. 각각의 문자열에는 중복된 문자가 존재하지 않는다. 문자열 S에 있는 문자 중 임의로 k개를 선택하여 문자열 S에서의 순서를 유지하여 만든 모든 부분 문자열을 모아 놓은 집합을 문자열 S에 대한 조합 C(S, k)라고 하자. 예를 들어, 문자열 S = 'abc'에 대한 조합 C(S, 2) = {'ab', 'ac', 'bc'}이다. 입력으로 문자열 X, Y, Z와 정수 k가 주어질 때 C(X, k), C(Y, k), C(Z, k)에 두 번 이상 나타나는 부분 문자열을 오름차순으로 출력하자.

입력

첫 번째 줄에 문자열 X가 주어진다.

두 번째 줄에 문자열 Y가 주어진다.

세 번째 줄에 문자열 Z가 주어진다.

네 번째 줄에 정수 k가 주어진다.

출력

C(X, k), C(Y, k), C(Z, k)에 두 번 이상 나타나는 부분 문자열을 오름차순으로 출력한다. 한 줄에 하나의 부분 문자열을 출력한다. 두 번 이상 나타나는 부분 문자열이 없으면 -1을 출력한다.

제한

  • 1 ≤ 문자열 X, Y, Z의 길이 ≤ 17
  • 1 ≤ k ≤ 문자열 X, Y, Z 길이의 최솟값
  • 문자열 X에는 중복된 문자가 존재하지 않는다.
  • 문자열 Y에는 중복된 문자가 존재하지 않는다.
  • 문자열 Z에는 중복된 문자가 존재하지 않는다.

예제 입력 1

a
a
a
1

예제 출력 1

a

예제 입력 2

ab
ba
ac
1

예제 출력 2

a
b

예제 입력 3

abc
acde
cde
2

예제 출력 3

ac
cd
ce
de

예제 입력 4

a
b
cde
1

예제 출력 4

-1

출처