URI Online Judge | 2126

Searching Subsequences

By Igor Gomes, UEVA BR Brazil

Timelimit: 1

Given two natural numbers N1 and N2, it is said that N1 is contiguous subsequence of N2 if in N1 appear all digits in the same order and contiguously. Create an program that reads two natural numbers and write if the first is a contiguous subsequence of the second.

Input

The input consists of several test cases and ends with the end of file (EOF). The first line of each entry is composed of anatural value N1 (1 <N1 <1010), the second line is composed of a value N2 (N1 <N2<1032).

Output

For each test case print the amount of contiguous subsequences and the position where the substring starts, if there is more of a subsequence, print where it started the last substring. If no there subsequence, print "Nao existe subsequencia" (that means no there subsequence). Show the result as the sample output.

Input Sample Output Sample

78954
7895478954789547895447895478954
464133
1331646546874694
12
1231321455123214565423112

Caso #1:
Qtd.Subsequencias: 6
Pos: 27


Caso #2:
Nao existe subsequencia


Caso #3:
Qtd.Subsequencias: 3
Pos: 24