These problems are from the atcoder DP contest, and were transferred onto DMOJ. All problem statements were made by several atcoder users. As there is no access to the test data, all data is randomly generated. If there are issues with the statement or data, please contact Rimuru or Ninjaclasher on slack.

You are given strings ~s~ and ~t~. Find one longest string that is a subsequence of both ~s~ and ~t~.

Notes

A subsequence of a string ~x~ is the string obtained by removing zero or more characters from ~x~ and concatenating the remaining characters without changing the order.

Constraints

• ~s~ and ~t~ are strings consisting of lowercase English letters.
• ~1 \le \left | s \right |~, ~\left | t \right | \le 3000~

Input Specification

The first line of input will contain a string ~s~.

The second line of input will contain a string ~t~.

Output Specification

You are to print out, on a single line, one longest string that is a subsequence of both ~s~ and ~t~. If there are multiple such strings, any of them will be accepted.

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either one will be accepted.

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara