Lines

A string (A = a_1a_2...a_n) is considered a substring of another string (B = b_1b_2...b_m) if there is an index (k) ((1 $\le$ k $\le$ m-n+1)) such that (a_1 = b_k), (a_2 = b_k+1), ..., (a_n = b_k+n-1).

A string (B) is termed a superstring of (A) if (A) is a substring of (B).

A string (A = a_1a_2...a_n) is lexicographically smaller than a string (B = b_1b_2...b_m) if there exists an index (k) such that for all (1 $\le$ t $\le$ k), (a_t = b_t) holds, and either (a_k+1 < b_k+1), or the length of (A) is equal to (k) and the length of (B) is greater than (k).

Given strings (S) and (T), your task is to find a string that is both a substring of (S) and a superstring of (T). If multiple such strings exist, output the longest one. If there are several strings of the maximum length, choose the lexicographically smallest one.

Input

The first line contains the string (S) ((1 $\le$ |S| $\le$ 4000)). The second line contains the string (T) ((1 $\le$ |T| $\le$ 4000)). Both strings consist of lowercase Latin letters. Here, (|S|) and (|T|) represent the lengths of strings (S) and (T), respectively.

Output

Output the required string, or "NO SOLUTION" (without quotes) if no such string exists.

Examples