Cipher Decoder Choi Junmin

Mingyun often writes English letters to Sangbeom. When Junmin learned this, he intercepted one of the letters, but the letter had been encrypted word by word.

Changyoung told Junmin that one real sentence from the letter may be hidden somewhere inside the encrypted letter. The encrypted letter may also contain made-up parts that are unrelated to the real sentence. Junmin wants to find the earliest position where the given real sentence could appear in the encrypted letter.

The encryption rule is as follows.

Each word in the real sentence is always replaced by one word in the encrypted letter. Equal words must be replaced by equal words, and two different words cannot be replaced by the same word. A word may also be replaced by itself.

For instance, if the real sentence is doo doom chit doo doom chat and the replacements are doo -> a, doom -> b, chit -> c, and chat -> d, then the encrypted letter contains it as a b c a b d.

All words are lowercase and separated by spaces. A sentence is a consecutive sequence of words.

Given the real sentence, find the earliest starting position where it could appear in the encrypted letter.

The first line contains the encrypted letter. Its length does not exceed 10^6, and its end is marked with $. The $ marker is not part of the letter.

The second line contains the real sentence to find. Its length also does not exceed 10^6, and it has the same format as the encrypted letter, ending with $.

Print the earliest position where the given real sentence could appear in the encrypted letter. The position is the position of the first word of that occurrence.

The first word of the encrypted letter has position 1, the next word has position 2, and so on. You may assume that an answer always exists.

If there are multiple possible positions, print the smallest one.