문자열 집합 조합하기

알파벳 소문자로 이루어진 문자열 $X$, $Y$, $Z$가 주어진다. 각 문자열에는 중복된 문자가 없다.

문자열 $S$의 문자 중 임의로 $k$개를 골라 $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 \le |X|, |Y|, |Z| \le 17$
• $1 \le k \le \min(|X|, |Y|, |Z|)$
• 문자열 $X$에는 중복된 문자가 없다.
• 문자열 $Y$에는 중복된 문자가 없다.
• 문자열 $Z$에는 중복된 문자가 없다.