발코딩

창영이와 강산이는 아주 재미있는 게임을 한다. 바로 '발로 타자 치기'이다.

이 게임을 하려면 먼저 두 사람이 각자 단어를 하나씩 생각한다. 그런 다음 같은 컴퓨터 앞에 나란히 앉는데, 창영이는 왼쪽에, 강산이는 오른쪽에 앉는다.

키보드를 바닥에 내려놓고, 창영이는 오른발로, 강산이는 왼발로 각자 생각한 단어를 치기 시작한다. 두 사람은 서로 번갈아 가며 자신의 단어를 입력하는데, 한 번에 꼭 한 글자만 쳐야 하는 것은 아니다(여러 글자를 연달아 칠 수도 있다).

두 사람이 번갈아 입력해 화면에 나타난 단어를 보고, 선영이는 각 알파벳을 누가 쳤는지 알아내려고 한다.

예를 들어 창영이가 'weissblume', 강산이가 'exupery'를 생각하고, 서로 번갈아 적절히 타자를 쳐서 화면에 'weeisxsbulupmerey'가 입력되었다고 하자. 이때 선영이는 각 위치마다 1(창영이가 친 글자) 또는 2(강산이가 친 글자)를 적어, 어떤 사람이 그 알파벳을 쳤는지 나타낸다.

두 사람은 항상 자신의 단어를 순서대로 입력하며, 중간에 글자를 빼먹지 않는다. 또한 오랜 연습 덕분에 오타도 발생하지 않는다. 즉 화면의 단어는 두 사람의 단어를 각자의 순서를 유지한 채 뒤섞어 놓은 것이다.

두 사람이 생각한 단어와 화면에 입력된 단어가 주어질 때, 각 알파벳을 누가 입력했는지 구하는 프로그램을 작성하시오.

첫째 줄에 창영이가 생각한 단어, 둘째 줄에 강산이가 생각한 단어가 주어진다. 두 단어는 모두 알파벳 소문자로만 이루어져 있으며, 길이는 각각 최대 150이다.

셋째 줄에 화면에 입력된 단어가 주어진다. 이 단어의 길이는 두 단어의 길이의 합과 같다.

입력은 항상 답이 존재하는 경우만 주어진다.

첫째 줄에 각 알파벳을 누가 입력했는지를 나타내는, 1과 2로 이루어진 문자열을 출력한다. 왼쪽에서 i번째 문자가 1이면 화면 단어의 i번째 알파벳은 창영이가, 2이면 강산이가 입력한 것이다. 즉 1로 표시된 위치의 알파벳만 순서대로 이으면 창영이의 단어가, 2로 표시된 위치만 이으면 강산이의 단어가 되어야 한다.

조건을 만족하는 문자열이 여러 개라면, 그중 사전순으로 가장 앞서는(즉 1을 2보다 앞에 두는 쪽을 우선하는) 문자열을 출력한다.