描述

给定两个由小写字母组成的字符串 $a$ 和 $b$，请输出最长的字符串 $x$，满足以下条件：$x$ 的某个排列是 $a$ 的子序列，且 $x$ 的某个排列也是 $b$ 的子序列。如果存在多个满足条件的 $x$，则选择字母序最小的一个。

输入

输入由多对字符串组成。每对的第一行是字符串 $a$，第二行是字符串 $b$。每个字符串单独占一行，且长度不超过 $1,000$ 个小写字母。

输出

对于每对输入字符串，输出满足条件的字符串 $x$。如果有多个 $x$ 满足条件，则选择字母序最小的一个。

输入数据 1

pretty  
women  
walking  
down  
the  
street  

输出数据 1

e  
nw  
et  

来源

The UofA Local 1999.10.16