ADAPHOTO - Ada and Terramorphing

给定两个串，全部由字符'-','^','~','v'构成，求这两个串的最长公共字串 $|S|\le 10^6$

Ada the Ladybug was already on two trips this year. She visited two countires: Republic of Bugongo and Democratic Republic of Bugongo. Even though those countires are completely different and far far away from each other, Ada found some similarities. Now she is looking at photos from each of those countries and examines similarities. Sadly, both of the sequences of photos are very long so she can't handle it herself. The sequence of photos is sequence of following terrestical formations: A hill (^), a valley (v), a plain (-), a lake ~ Find the longest common contigous subsequence between the two sequences of photos. **Important note:** Teramorphism is very difficult process. One can't eassily influence it so each of the terrestical formation is generated with more or less 25%.

The first two and the only lines of input contigous first and second sequence of photos **1**

For each test-cases, print the longest common sequence.