Bessie sucht Kühe für ihren Buchclub. Die Herde hat $N$ Kühe ($2 \le N \le 50,000$), nummeriert $1\ldots N$, aber sie möchte nur die urteilsfähigsten und geselligsten.

Wie eine Partnervermittlung erstellt sie einen Fragebogen und lässt jede der $N$ Kühe die $NQ$ Fragen ($1 \le NQ \le 50$), genannt $R_{1}\ldots R_{NQ}$, beantworten. Etwa: „Wie gern liest du Science-Fiction?“ Jede Antwort ist eine ganze Zahl in $1\ldots 5$.

Werte die Ergebnisse aus und beantworte etwa: „Wie viele Kühe antworteten 2 auf Frage 3, 4 auf Frage 7 und 1 auf Frage 8?“ Die Anfrage hat $P$ Teile ($1 \le P \le 10$), jeweils mit $Qj$ ($1 \le Qj \le NQ$) und $Aj$ ($1 \le Aj \le 5$), Fragennummer und verlangter Antwort. Gib als ganze Zahl aus, wie viele Kühe für jedes $j\in\{1,\ldots,P\}$ auf $Qj$ mit $Aj$ antworteten.

Für 4 Kühe und 5 Fragen lauten die Antworten:

Auf „Wie viele antworteten 2 auf Frage 1 und 1 auf Frage 2?“ ist die Antwort 1, nur Kuh 4. Auf „Wie viele antworteten 1 auf Frage 1 und Frage 3?“ ist sie 2, Kühe 1 und 3.

Eingabe

• Zeile 1: drei durch Leerzeichen getrennte ganze Zahlen $N$, $NQ$ und $P$.
• Zeilen $2\ldots N+1$: Zeile $i+1$ enthält $NQ$ durch Leerzeichen getrennte ganze Zahlen, Antworten der Kuh $i$: $R_{1}\ldots R_{NQ}$.
• Zeilen $N+2\ldots N+1+P$: Zeile $j+N+1$ enthält zwei durch ein Leerzeichen getrennte ganze Zahlen $Qj$ und $Aj$.

Ausgabe

• Zeile 1: eine ganze Zahl, die Anzahl Kühe, die alle Kriterien von Bessie erfüllen.

Beispiele

Eingabe 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

Ausgabe 1

2

Aufgabenautor: Rob Kolstad, 2010