서로소 정규 표현식

마크(Mark)는 포보스(Phobos)와 데이모스(Deimos)의 주민을 위한 새로운 소셜 네트워크 페이스팜(Facepalm)을 만들고 있다. 그는 각 계정에 대해 로그인 시 기본으로 추천할 고향 소행성을 제시하려 하는데, 사용자의 고향 소행성은 그 사람의 성(last name)을 분석해 알아낼 수 있다는 사실을 발견했다.

모든 성은 영어 소문자로 이루어진, 비어 있지 않은 단어이다. 포보스 사용자의 성은 정규 표현식 $P$와 일치하고, 데이모스 사용자의 성은 정규 표현식 $D$와 일치한다.

문제는 어떤 성이 두 표현식 모두와 일치할 수 있다는 점이다. 두 표현식이 서로소라는 것은, 두 표현식 모두와 일치하는 비어 있지 않은 문자열 $s$가 존재하지 않음을 뜻한다. 마크는 $P$와 $D$가 서로소라고 믿지만, 이를 확인하려면 당신의 도움이 필요하다.

두 정규 표현식 $P$와 $D$가 주어진다. 두 표현식이 서로소인지 판별하고, 서로소가 아니라면 두 표현식 모두와 일치하는 가장 짧은, 비어 있지 않은 문자열을 구하라. 그러한 문자열이 여러 개라면 사전순으로 가장 앞서는 것을 출력한다.

입력은 두 줄로 이루어진다. 첫 번째 줄에는 정규 표현식 $P$가, 두 번째 줄에는 정규 표현식 $D$가 주어진다. 각 표현식의 길이는 $1$ 이상 $100$ 이하이다.

두 표현식이 서로소이면 첫 번째 줄에 Correct를 출력한다.

서로소가 아니면 첫 번째 줄에 Wrong을 출력하고, 두 번째 줄에 두 표현식 모두와 일치하는 가장 짧은, 비어 있지 않은 문자열을 출력한다. 그러한 문자열이 여러 개라면 사전순으로 가장 앞서는 것을 출력한다.

정규 표현식과 그에 일치하는 문자열은 다음과 같이 정의된다.

• 하나의 소문자 $c$는 정규 표현식이며, 오직 한 글자 $c$로 이루어진 문자열과만 일치한다.
• 선택(alternation): $P$와 $Q$가 정규 표현식이면 $(P \mid Q)$도 정규 표현식이며, 문자열 $\alpha$는 $\alpha$가 $P$ 또는 $Q$와 일치하면 이 표현식과 일치한다.
• 이어 붙이기(concatenation): $P$와 $Q$가 정규 표현식이면 $(PQ)$도 정규 표현식이며, 문자열 $\alpha$는 $\alpha = \beta\gamma$로 나누어 $\beta$가 $P$와, $\gamma$가 $Q$와 일치하면 이 표현식과 일치한다.
• 클레이니 스타(Kleene star): $P$가 정규 표현식이면 $(P^{*})$도 정규 표현식이며, 문자열 $\alpha$는 $\alpha$를 $P$와 각각 일치하는 0개 이상의 조각 $\alpha_1\alpha_2\dots\alpha_k$로 나눌 수 있으면 이 표현식과 일치한다. 빈 문자열은 항상 클레이니 스타와 일치한다.

입력에서 표현식은 그룹을 묶기 위한 괄호와 함께 일반적인 연산자 우선순위로 표기된다. 클레이니 스타 *가 가장 강하게 결합하고, 그다음이 이어 붙이기, 마지막이 선택 |이다. 예를 들어 a(ab)*b는 글자 a 다음에 ab가 0번 이상 반복되고 그 뒤에 글자 b가 오는 것을 뜻한다.