After getting tired of solving various longest common substring and subsequence problems, you decide to do the opposite.

A "substring" of a string refers to a contiguous segment of it; for example, bcd is a substring of abcdef, but bde is not.

A "subsequence" of a string refers to a segment that does not have to be contiguous; for example, bde is a subsequence of abcdef, but bdd is not.

Given two strings $A$ and $B$ consisting of lowercase letters, please calculate:

(1) The length of the shortest substring of $A$ that is not a substring of $B$. (2) The length of the shortest substring of $A$ that is not a subsequence of $B$. (3) The length of the shortest subsequence of $A$ that is not a substring of $B$. (4) The length of the shortest subsequence of $A$ that is not a subsequence of $B$.

Input

The input contains two lines, each containing a string of lowercase letters, representing $A$ and $B$ respectively.

Output

Output 4 lines, each containing an integer representing the length of the answer to the above 4 problems. If no such answer exists, output -1.

Examples

Input 1

aabbcc
abcabc

Output 1

2
4
2
4

Input 2

aabbcc
aabbcc

Output 2

-1
-1
-1
-1

Constraints

• For 20% of the data, the lengths of $A$ and $B$ do not exceed 20.
• For 50% of the data, the lengths of $A$ and $B$ do not exceed 500.
• For 100% of the data, the lengths of $A$ and $B$ do not exceed 2000.