시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 441 83 60 17.647%

문제

알파벳 소문자로 이루어진 두 문자열 a와 b에 대해, a의 부분 수열의 순열이자 b의 부분 수열의 순열이 되는 가장 긴 문자열 x를 구하여라.

입력

각각의 입력은 한 쌍의 줄로 이루어져 있다.

첫 줄에는 문자열 a가 두 번째 줄에는 문자열 b가 주어진다.

각각의 문자열은 줄로 구분되며, 최대 1000개의 알파벳 소문자로 이루어졌다.

출력

각각의 입력에 대해, x를 출력한다.

가능한 x가 여러 개 존재하는 경우, 사전순으로 가장 앞에 오는 것을 출력한다.

예제 입력 1

pretty
women
walking
down
the
street

예제 출력 1

e
nw
et
W3sicHJvYmxlbV9pZCI6IjE2MjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjVcdWQxYjUgXHVjMjFjXHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0IGFcdWM2NDAgYlx1YzVkMCBcdWIzMDBcdWQ1NzQsIGFcdWM3NTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWMyMWNcdWM1ZjRcdWM3NzRcdWM3OTAgYlx1Yzc1OCZuYnNwO1x1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjMjFjXHVjNWY0XHVjNzc0IFx1YjQxOFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YmIzOFx1Yzc5MFx1YzVmNCB4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NDAgXHVkNTVjIFx1YzMwZFx1Yzc1OCZuYnNwO1x1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCBhXHVhYzAwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM5MDRcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHViYTcwLCBcdWNkNWNcdWIzMDAgMTAwMFx1YWMxY1x1Yzc1OCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1Yzg0Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjNzg1XHViODI1XHVjNWQwIFx1YjMwMFx1ZDU3NCwmbmJzcDt4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHViMmE1XHVkNTVjIHhcdWFjMDAgXHVjNWVjXHViN2VjJm5ic3A7XHVhYzFjIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjAsIFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjNWQwIFx1YzYyNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE2MjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb21tb24gcGVybXV0YXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIHR3byBzdHJpbmdzIG9mIGxvd2VyY2FzZSBsZXR0ZXJzLCBhIGFuZCBiLCBwcmludCB0aGUgbG9uZ2VzdCBzdHJpbmcgeCBvZiBsb3dlcmNhc2UgbGV0dGVycyBzdWNoIHRoYXQgdGhlcmUgaXMgYSBwZXJtdXRhdGlvbiBvZiB4IHRoYXQgaXMgYSBzdWJzZXF1ZW5jZSBvZiBhIGFuZCB0aGVyZSBpcyBhIHBlcm11dGF0aW9uIG9mIHggdGhhdCBpcyBhIHN1YnNlcXVlbmNlIG9mIGIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBjb25zaXN0cyBvZiBwYWlycyBvZiBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgb2YgYSBwYWlyIGNvbnRhaW5zIGEgYW5kIHRoZSBzZWNvbmQgY29udGFpbnMgYi4gRWFjaCBzdHJpbmcgaXMgb24gYSBzZXBhcmF0ZSBsaW5lIGFuZCBjb25zaXN0cyBvZiBhdCBtb3N0IDEsMDAwIGxvd2VyY2FzZSBsZXR0ZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHN1YnNlcXVlbnQgcGFpciBvZiBpbnB1dCBsaW5lcywgb3V0cHV0IGEgbGluZSBjb250YWluaW5nIHguIElmIHNldmVyYWwgeCBzYXRpc2Z5IHRoZSBjcml0ZXJpYSBhYm92ZSwgY2hvb3NlIHRoZSBmaXJzdCBvbmUgaW4gYWxwaGFiZXRpY2FsIG9yZGVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==