You are in charge of data transfer between two Data Centers. Each set of data is represented by a pair of strings. Over a period of time you have observed a trend: most of the times both strings share some prefix. You want to utilize this observation to design a data compression algorithm which will be used to reduce amount of data to be transferred.
You are given two strings, and , representing the data, you need to find the longest common prefix () of the two strings. Then you will send substring , and , where and are the substring left after stripping from them.
For example, if "abcdefpr" and "abcpqr", then "abc", "defpr", "pqr".
Input Format
The first line contains a single string denoting .
The second line contains a single string denoting .
Constraints
- and will contain only lowercase Latin characters ('a'-'z').
Output Format
In first line, print the length of substring , followed by prefix . In second line, print the length of substring , followed by substring . Similary in third line, print the length of substring , followed by substring .
Sample Input 0
abcdefpr
abcpqr
Sample Output 0
3 abc
5 defpr
3 pqr
Sample Input 1
kitkat
kit
Sample Output 1
3 kit
3 kat
0
Sample Input 2
puppy
puppy
Sample Output 2
5 puppy
0
0
Explanation
Sample Case 0:
Already explained above in the problem statement.
Sample Case 1:
"kit", which is also . So will be "kat" and will be an empty string.
Sample Case 2:
Because both strings are the same, the prefix will cover both the strings. Thus, and will be empty strings.