아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

노래 맞히기

시간 제한1초메모리 제한128 MB

요약
제목 단어들과 순서대로 주어지는 가사를 훑으며 서로 다른 제목 단어의 절반 이상이 처음 나타나는 가사 위치를 구합니다.
난이도

쉬움10점 중 2점

유형
시뮬레이션, 해시맵
정답자
아직 제출이 없습니다

문제

"노래 맞히기"는 젊은 프로그래머들 사이에서 인기 있는 게임이다. 순발력과 지혜, 인내심을 겨루는 놀이다. 진행자가 모두에게 들리도록 노래를 틀면, 참가자들은 그 노래의 제목을 최대한 빨리 맞히려고 경쟁한다.

미르코는 노래 맞히기의 세계적인 고수다. 그는 제목에 들어 있는 단어 중 절반 이상이 가사에서 나오는 순간 바로 제목을 외친다. 제목의 단어는 모두 서로 다르다. 즉, 같은 단어가 제목에 두 번 이상 나오지 않는다.

노래 제목과 가사가 주어질 때, 미르코가 가사의 몇 번째 단어에서 제목을 맞히는지 구하여라.

입력

첫째 줄에 제목에 들어 있는 단어의 개수 NN (1≤N≤501 \le N \le 50)이 주어진다.

다음 NN개의 줄에는 제목의 단어가 한 줄에 하나씩 주어진다.

그다음 줄에는 가사에 들어 있는 단어의 개수 MM (1≤M≤100001 \le M \le 10000)이 주어진다.

다음 MM개의 줄에는 가사의 단어가 한 줄에 하나씩 주어진다.

제목과 가사의 모든 단어는 11자 이상 1515자 이하의 영어 소문자로 이루어져 있다. 미르코는 항상 가사에서 제목을 맞힐 수 있도록 입력이 주어진다.

출력

제목의 단어 중 절반 이상이 가사에 등장하는 순간, 즉 미르코가 제목을 맞히는 시점까지 읽은 가사 단어의 개수를 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    3
    sedam
    gladnih
    patuljaka
    7
    sedam
    dana
    sedam
    noci
    sedam
    gladnih
    godina
    
    예상 출력
    6
    
  2. 예제 2

    입력
    4
    moj
    bicikl
    mali
    crveni
    11
    ja
    vozim
    bicikl
    crvene
    boje
    ali
    je
    moj
    moj
    samo
    moj
    
    예상 출력
    8