HARSTR - TWO STRINGS

no tags 

You are given two strings a and b. You have to remove the minimum possible number of consecutive (standing one after another) characters from string b in such a way that it becomes a submultiset of string a. It can happen that you will not need to remove any characters at all, or maybe you will have to remove all of the characters from b and make it empty.

Input

The first line contains string a, and the second line contains string b. Both of these strings are non-empty and consist of lowercase letters of English alphabet. The length of each string is no bigger than 105 characters.

Output

On the first line output a submultiset of string a in sorted order, obtained from b. If multiple answers exist, output lexicographically smallest.

If the answer consists of zero characters, output "-" (a minus sign).

Example

Input:
abacaba
abcdcba

Output:
aabbc
Input:
abcdy
abdxybc

Output:
abcd

Note: ouput is abcd not abcy since abcd is lexicographically smaller.


hide comments
:D: 2018-10-25 02:02:49

re kush_pathak01: to get 'abcdy' from 'abdxybc' we need to remove 'x' and one 'b', so this means either 'bdx' or 'xyb' (we must remove consecutive characters). Either way we are left with 'abcy' or 'abcd'. 'abcdy' is not possible.

kush_pathak01: 2017-11-05 15:22:15

why in second input abcdy cannot be the answer??

anonymous: 2017-03-24 17:50:55

It should be lexicographically smallest solution before sorting or after sorting?

abdou_93: 2017-02-05 18:27:15

@author can you check my submission id (18705906)
RE: check for corner cases , u missing something!!

Last edit: 2017-02-05 18:42:13
wisfaq: 2017-02-02 20:26:39

aabbc is not a set but a multiset:
https://en.wikipedia.org/wiki/Multiset
So the answer for the problem is not a set but a multiset.
RE: Thanks:)

You should make it a "submultiset"

Last edit: 2017-02-03 20:30:52
Vipul Srivastava: 2017-02-02 18:45:16

can you please give me an example where its not happening?
RE : its sorted now , look for bug in your program:)

Last edit: 2017-02-02 19:05:34
Vipul Srivastava: 2017-02-02 18:30:27

@author can you please check if submission and point me to where I am going wrong?
RE: u have to output sorted subset;

Last edit: 2017-02-02 18:41:21
sanju04: 2017-02-02 11:15:02

awesome... amazing!!!!!


Added by:har_vi
Date:2017-01-29
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Codeforces , @nonushikhar