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".
The first line contains a single string denoting .
The second line contains a single string denoting .
and will contain only lowercase Latin characters ('a'-'z').
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
Sample Output 0
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
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.