Bessie는 독서 모임에 들어올 소를 찾습니다. 무리에는 $1\ldots N$으로 번호 붙인 소 $N$마리($2 \le N \le 50,000$)가 있지만 가장 안목 있고 사교적인 소만 원합니다.

소개 서비스처럼 설문을 만들고 $N$마리의 소 각각에게 $R_{1}\ldots R_{NQ}$라는 $NQ$개 질문($1 \le NQ \le 50$)에 답하게 합니다. “공상 과학 소설 읽기를 얼마나 좋아하나요?” 같은 질문이며 답은 $1\ldots 5$의 정수입니다.

결과를 집계하고 “질문 3에 2, 질문 7에 4, 질문 8에도 1이라 답한 소는 몇 마리인가?” 같은 문제에 답합니다. 집계 질문은 $P$개 조건($1 \le P \le 10$)으로, 각 조건의 $Qj$($1 \le Qj \le NQ$)와 $Aj$($1 \le Aj \le 5$)는 질문 번호와 요구 답입니다. 모든 $j\in\{1,\ldots,P\}$에 대해 $Qj$에 $Aj$로 답한 소의 총수를 정수 하나로 출력합니다.

소 4마리와 질문 5개일 때 답은 다음과 같습니다.

“질문 1에 2, 질문 2에 1이라 답한 소는?”의 답은 1, 소 4뿐입니다. “질문 1과 질문 3 모두에 1이라 답한 소는?”의 답은 2, 소 1과 3입니다.

입력

• 줄 1: 공백으로 구분한 세 정수 $N$, $NQ$, $P$.
• 줄 $2\ldots N+1$: 줄 $i+1$은 소 $i$의 답 $R_{1}\ldots R_{NQ}$인 공백 구분 정수 $NQ$개를 담습니다.
• 줄 $N+2\ldots N+1+P$: 줄 $j+N+1$에는 공백으로 구분한 두 정수 $Qj$와 $Aj$가 있습니다.

출력

• 줄 1: Bessie의 모든 조건을 만족하는 소의 수인 정수 하나.

예제

입력 1

4 5 2
1 1 1 1 1
1 2 3 4 5
1 2 1 2 3
2 1 1 2 2
1 1
3 1

출력 1

2

문제 출제: Rob Kolstad, 2010