암호 해독가 최준민

민균이는 상범이에게 영어로 편지를 자주 보낸다. 이 사실을 알게 된 준민이는 편지를 가로채 내용을 읽으려 했지만, 편지는 단어 단위로 암호화되어 있었다.

창영이는 준민이에게 암호화된 편지 안에 진짜 편지의 한 문장이 숨어 있을 수 있다고 알려 주었다. 편지에는 진짜 문장과 같은 규칙으로 만들어진 부분도 있고, 실제 문장과 관계없는 꾸며낸 부분도 있을 수 있다. 준민이는 암호화된 편지에서 주어진 진짜 문장이 가장 먼저 나타날 수 있는 위치를 찾으려 한다.

암호화 규칙은 다음과 같다.

진짜 문장에 등장하는 각 단어는 암호화된 편지에서 어떤 단어 하나로 항상 바뀐다. 같은 단어는 항상 같은 단어로 바뀌며, 서로 다른 두 단어가 같은 단어로 바뀔 수는 없다. 단어가 자기 자신으로 바뀌는 것도 가능하다.

예를 들어 진짜 문장이 doo doom chit doo doom chat이고 doo -> a, doom -> b, chit -> c, chat -> d로 바뀐다면, 암호화된 편지에는 a b c a b d로 나타난다.

모든 단어는 소문자이며 공백으로 구분된다. 문장은 여러 단어가 연속된 것이다.

주어진 진짜 문장이 암호화된 편지에서 가장 먼저 나타날 수 있는 시작 위치를 구하라.

첫 줄에는 암호화된 편지가 주어진다. 편지의 전체 길이는 10^6을 넘지 않으며, 끝은 $로 표시된다. $는 편지의 단어에 포함되지 않는다.

둘째 줄에는 찾고 싶은 진짜 문장이 주어진다. 이 문장의 길이도 10^6을 넘지 않으며, 암호화된 편지와 같은 형식으로 끝에 $가 붙는다.

주어진 진짜 문장이 암호화된 편지에서 가장 먼저 나타날 수 있는 위치를 출력한다. 위치는 해당 구간의 첫 단어 위치이다.

암호화된 편지의 첫 단어 위치는 1, 다음 단어 위치는 2이다. 답은 항상 존재한다고 가정해도 좋다.

가능한 위치가 여러 개이면 가장 작은 위치를 출력한다.