2019 ICPC NENA (Quebec) Regional Qualifier

Start

2019-10-26 05:00 AKDT

2019 ICPC NENA (Quebec) Regional Qualifier

End

2019-10-26 11:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -370 days 0:40:08

Time elapsed

6:00:00

Time remaining

0:00:00

Problem B
Paranoid

Either you are paranoid, or the CIA is sending you hidden messages in the newspaper. Every day you find an article that has a message hidden by separating its characters with other letters. You go through the article, circling every few characters, until the message is revealed. However, this is a tedious process, so you would love to write a program to ease the burden.

You are given a text and a target string (the hidden message). You must write a program that finds the shortest substring of characters in the text that contains the target string as a (not necessarily contiguous) subsequence.

Input

The input consists of some number of pairs of texts and targets, each on their own line. The end of the file indicates the end of the input. The text and target are separated by an equals sign ($=$). The target will always appear in the text. The text will contain at most $10\, 000$ characters.

Output

For each text/target pair, you should output the start and end indices, separated by a space, of the shortest substring of the text that contains the target as a (not necessarily contiguous) subsequence. Indices into the text start at $0$. If the target appears more than once with the same length subsequence, you should output the indices of the first appearance.

Sample Input 1 Sample Output 1
HATCATBAT=CAT
HATCTABTA=CAT
don't forget dozens of hotdogs=food
ZABCDEFGAABAABFGZERARBR=ABG
this is not a conspiracy theory "at the moment".=tin hat
3 5
3 7
6 26
12 15
0 34