시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB3301258839.640%

문제

n명의 학생에게 다음과 같이 선호도를 조사하였다. 각 학생은 아래 세 가지 조사 항목 각각에 대하여 반드시 1가지를 선택해야 한다.

  • 좋아하는 과목(subject)에 'kor', 'eng', 'math' 중 하나를 선택
  • 좋아하는 과일(fruit)에 'apple', 'pear', 'orange' 중 하나를 선택
  • 좋아하는 색깔(color)에 'red', 'blue', 'green' 중 하나를 선택

n명 학생의 선호도에 대하여 m개의 질의를 순서대로 처리하자. 하나의 질의는 다음과 같다.

  • 질의 형식은 'subject fruit color'이다.
  • subject은 'kor', 'eng', 'math', '-' 중 하나이다.
  • fruit은 'apple', 'pear', 'orange', '-' 중 하나이다.
  • color는 'red', 'blue', 'green', '-' 중 하나이다.
  • '-' 표시는 해당 조건을 고려하지 않겠다는 의미이다.
  • n명 학생 중 선호도가 subject fruit color와 일치하는 학생 수를 출력한다.

n명 학생의 선호도와 m개의 질의가 주어 지면, m개의 질의를 순서대로 처리하자. n과 m이 매우 커서 고민하고 있는 우리 학생들을 도와주자.

입력

첫 번째 줄에 n과 m이 공백을 사이에 두고 순서대로 주어진다.

두 번째 줄부터 n개의 줄에 학생들의 선호도가 주어진다. 한 줄에 한 학생의 선호도가 주어진다. 한 학생의 선호도는 학생이 좋아하는 과목, 과일, 색깔을 공백을 사이에 두고 순서대로 주어진다. 

다음 줄부터 m개의 줄에 질의가 주어진다. 한 줄에 하나의 질의가 주어진다. 하나의 질의는 과목, 과일, 색깔을 공백을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄부터 m개의 줄에 질의 결과를 순서대로 출력한다. 한 줄에 하나의 질의 결과를 나타내는 정수를 출력한다.

제한

  • 1 ≤ n, m ≤ 100,000

예제 입력 1

5 4
kor apple red
kor pear blue
eng apple red
eng orange blue
math apple green
kor apple red
kor - blue
eng - -
- - red

예제 출력 1

1
1
2
2

첫 번째 질의 kor apple red와 일치하는 학생은 첫 번째 학생이다.

두 번째 질의 kor - blue와 일치하는 학생은 두 번째 학생이다.

세 번째 질의 eng - -와 일치하는 학생은 세 번째, 네 번째 학생이다.

네 번째 질의 - - red와 일치하는 학생은 첫 번째, 세 번째 학생이다.

출처