Problem Description

Given a plaintext and a portion of ciphertext. Both the plaintext and ciphertext consist of English words, and each word in the ciphertext corresponds to a word in the plaintext.

Determine the earliest possible position in the plaintext where the given ciphertext could appear.

Input Format

The first line contains several English words followed by a $\texttt{\$}$, representing the plaintext.

The second line contains several English words followed by a $\texttt{\$}$, representing the ciphertext.

The $\texttt{\$}$ at the end of each line indicates the end of that line. The data guarantees that there will not be multiple $\texttt{$}$ symbols on the same line.

Output Format

Output the earliest possible position in the plaintext where the first word of the ciphertext could appear.

Sample Input and Output

Input Sample #1

a a a b c d a b c $
x y $

Output Sample #1

3

Input Sample #2

xyz abc abc xyz $
abc abc $

Output Sample #2

2

Input Sample #3

a b c x c z z a b c $
prvi dr prvi tr tr x $

Output Sample #3

3

Notes

[Data Size and Constraints]

• For $100\%$ of the data, the lengths of the plaintext and ciphertext strings do not exceed $10^6$, and all input words are composed of lowercase letters.

[Hints and Notes]

This problem is translated from COCI 2011-2012 CONTEST #4 Task 6 KRIPTOGRAM.

The score for this problem is set according to the original COCI, with a maximum of $140$.

见题面 Input 部分

见题面 Output 部分