By Victor Jatobá and Ariane Machado, USP Brazil
The Eachians are still worried after They found out a new bomb and received a mount of texts from the neighboring planet. They still suspect that there is a pattern in the number represented by a word position in the text. These positions together, they say, represents a key to deactivate a bomb that is about to explode the EACH planet.
You were then summoned to developing a program that receive a set of a little texts followed by the words and the program need to return the first position of each word that is present in each text.
Word: can contain only lowercase letters of the alphabet ('a'-'z').
Text: can contain only lowercase letters of the alphabet ('a'-'z') separated by one whitespace. Text contains no line break ('\n') and no special characters.
The size of the words will be never greater than the size of the text.
Position: You should consider that the first position of the text should be position 0 (zero). Thus, in a text with 50 characters, the last position will be the 49.
You should only search for the exactly word. For example, the word SHIP is different from FRIENDSHIP.
The input need be, exactly:
The first line: The N amount of the texts followed by word that must be read (2 ≤ N ≤ 100.000). There is a word for each text.
For the next lines, for each input, the program will be received, respectively:
The text, that contains N characters (10 ≤ N ≤ 128).
The word to be found in the text, that contains M characters (2 ≤ M ≤ 128).
For each pair of text and word, the program must print the position of the first letter present in the text. Mind that the words can be repeated in the text. In this instance, the positions must be printed one in front of other, separated with whitespaces. If the text doesn’t contain the word, return -1 (the number minus one).
|Input Samples||Output Samples|