Problem I. Ichthyology

Author:I. Tufanov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Scientists of Nearsea Institute of Linguistic Ichthyology study the fish language. They found few specific sounds which some fishes can emit, and assign letters of Latin alphabet to them. Then they took an underwater sound record and used state-of-the-art pattern recognition software to convert it into a string of letters.

They hypothesize that one sub-string of letters may have particular meaning in the fish language (sand so serve as a kind of "word"), and so they want to calculate how often that sub-string may have been used during the record.

You program must, given the strings T and W, find minimum and maximum number of non-overlapping occurrences of W in T.

For example, if W="abab" and T="ababbbabababab", the string may be interpreted as "(abab)bb(abab)(abab)" (giving 3 occurrences) or as "(abab)bbab(abab)ab" (giving 2 occurrences). So, the minimal number is 2 and the maximum is 3.

Input file format

First line of input file contains string W. Second line of input file contains string T.

Output file format

Output file should contain two integers — minimum and maximum number of non-overlapping occurrences of W in T.

Constraints

1 ≤ length(W) ≤ 100;

1 ≤ length(T) ≤ 1000;

W and T contain small Latin letters only.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
a
b
0 0
2
qq
qqaqqqaqqqq
3 4

0.036s 0.007s 15