Problem Setter: Mimsad Ahmed Hridoy

Intake 33, Department of CSE

Little hackers Andrew and Beth are trying to find some secret information in a long log of the chat conversation of their friend Chris. They know that the secret part of the conversation is related to the message to his friend Dan they intercepted before. But the log is too long to search by hand. Therefore they decided to find the parts that are most similar to the message to analyze them later. They ask you to help them to write the corresponding program.

 

Let us represent the log as one string t with all spaces, line feeds, digits and punctuation marks deleted. We will also ignore the case of the letters. Thus, the string only consists of capital letters of the English alphabet. The message, in turn, is also converted to the same form, let us denote the corresponding string as p.

 

For each position, i in t Andrew and Beth want to find the length of the maximal substring of p that starts in t at i’th position. Thus, for each i you have to find such j = j(i) that t[i . . . i+j -1] = p[k . . . k +j -1] for some k, and j is maximal possible.

Input Format

The input file contains two lines. The first line contains t, the second line contains p. The length of t does not exceed 100, the length of p does not exceed 100. Both strings are not empty.

 

Input only consists of capital letters of the English alphabet.

Output Format

Let the length of t be n. Output n numbers — for each i output the corresponding j(i).

Samples