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 subsequence 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.

Subsequence of string s is any such string that can be obtained by erasing zero or more characters (not necessarily consecutive) from string s.

Input

The first line contains string a, and the second line — string b. Both of these strings are nonempty 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 subsequence of string a, obtained from b by erasing the minimum number of consecutive characters.

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

Examples

Input

hi
bob


Output

-


Input

abca
accepted


Output

ac


Input

abacaba
abcdcba


Output

abcba

Note

In the first example strings a and b don't share any symbols, so the longest string that you can get is empty.

In the second example ac is a subsequence of a, and at the same time you can obtain it by erasing consecutive symbols cepted from string b.
/** This is a solution to the problem Two Strings on codeforces
 * 
 * Given two strings x and y, compute the longest subsequence of x and y,
 * when only consecutive characters in y may be deleted.
 * 
 * For details, see:
 * http://codeforces.com/problemset/problem/762/C
 */

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class TwoStrings {

	public static void main(String[] args) throws IOException {
		long start = System.nanoTime();
		System.out.println(new TwoStrings().solve2(InputType.SYSTEMIN));
		long end = System.nanoTime();
//		System.out.println((end - start)/1000000 + "ms");
	}
	
	/*
	 * Idea2: 
	 * - Search longest prefix of y as subsequence in x : O(m + n)
	 * - Search longest suffix of y as subsequence in x : O(m + n)
	 * - In above steps, store positions of matching characters in arrays p and s, respectively
	 * - Find max_{i, j} {i + (n - j) | p(i) < s(j)} : O(n) !!
	 */
	private String solve2(InputType inputType) throws IOException {
		BufferedReader br;
		if(inputType == InputType.SYSTEMIN)
			br = new BufferedReader(new InputStreamReader(System.in));
		else
			br = new BufferedReader(new FileReader("input.txt"));
		
		String string = br.readLine();
		String pattern = br.readLine();
		
		br.close();
		
		int stringPos = 0;
		int prefixLength = 0;
		
		List<Integer> prefixMatchingCharacterPos = new ArrayList<>();
		
		// find prefix
		while(prefixLength != pattern.length() && stringPos != string.length()) {
			while(stringPos != string.length() && string.charAt(stringPos) != pattern.charAt(prefixLength)) {
				++stringPos;
			}
			if(stringPos == string.length()) break;
			prefixMatchingCharacterPos.add(stringPos);
			++prefixLength;
			++stringPos;
		}
		
		String longestSubsequence = getPrefixSuffixCombination(pattern, prefixLength, 0);
		if(longestSubsequence.length() == pattern.length()) return encodeIfEmpty(longestSubsequence, "-");
		
		stringPos = string.length() - 1;
		int suffixLength = 0;
		
		List<Integer> suffixMatchingCharacterPos = new ArrayList<>();
		
		// find suffix
		while(suffixLength != pattern.length() && stringPos >= 0) {
			while(stringPos >= 0 && string.charAt(stringPos) != pattern.charAt(pattern.length() - suffixLength - 1)) {
				--stringPos;
			}
			if(stringPos < 0) break;
			suffixMatchingCharacterPos.add(stringPos);
			++suffixLength;
			--stringPos;
		}
		
		longestSubsequence = longerOf(longestSubsequence, getPrefixSuffixCombination(pattern, 0, suffixLength));
		if(longestSubsequence.length() == pattern.length() - 1) return encodeIfEmpty(longestSubsequence, "-");
		
		// find maximal valid combination of prefix and suffix
		/*
		 * Pattern:		x x x x x x x x x x x x x x x x
		 *  Prefix:		- - - - - - - - - - -
		 *  Suffix:		                  - - - - - - -
		 *  PMCP  :		0 1 2 3 4 5 6 7 8 9 10 
		 *  SMCP  :                       6 5 4 3 2 1 0
		 *  preLen:		11
		 *  sufLen:		7
		 */
		
		int prefixPos = prefixLength - 1;
		int suffixPos = 0;
		// find prefixPos in suffixMatchingCharacterPos (linear search)
		while(prefixPos >= 0 && suffixPos < suffixLength) {
			suffixPos = findIndexOfFirstSmallerOrEqualElementStartAt(suffixPos, suffixMatchingCharacterPos, prefixMatchingCharacterPos.get(prefixPos));
			String curSubsequence = getPrefixSuffixCombination(pattern, prefixPos + 1, suffixPos);
			longestSubsequence = longerOf(curSubsequence, longestSubsequence);
			if(longestSubsequence.length() == pattern.length() - 1) return encodeIfEmpty(longestSubsequence, "-");
			--prefixPos;
		}
		
		return encodeIfEmpty(longestSubsequence, "-");
	}
	
	private String encodeIfEmpty(String string, String code) {
		if(string.length() == 0) return code;
		else return string;
	}
	
	
	private int findIndexOfFirstSmallerOrEqualElementStartAt(int curPos, List<Integer> descendingList, int element) {
		List<Integer> remainingRange = descendingList.subList(curPos, descendingList.size());
		int newPos = Collections.binarySearch(remainingRange, element, Comparator.reverseOrder());
		if(newPos >= 0) return newPos + curPos;
		else return -newPos - 1 + curPos;
		
//		while(curPos < descendingList.size() && descendingList.get(curPos) > element) {
//			curPos++;
//		}
//		return curPos;
	}
	
	private String getPrefixSuffixCombination(String pattern, int prefixLength, int suffixLength) {
		if(prefixLength + suffixLength > pattern.length()) return pattern;
		return pattern.substring(0, prefixLength) + pattern.substring(pattern.length() - suffixLength);
	}
	
	private String longerOf(String x, String y) {
		if(x.length() > y.length()) return x;
		return y;
	}
	
	private enum InputType {
		FILE, SYSTEMIN
	}
}
