A mountaintop observatory logs every calibration pass its night-shift astronomers run on the facility's shared telescope instruments. You are given the roster of astronomers, the catalogue of instruments, and a log of completed calibration passes. For every astronomer and every instrument, report how many times that astronomer completed a calibration pass on that instrument.

Input format

• Line 1: three space-separated integers n, m, and k — the number of astronomers on the roster, the number of instruments in the catalogue, and the number of calibration-pass log entries.
• The next n lines each contain an integer id and a string name — one astronomer's unique id and name.
• The next m lines each contain a single string instrument — one instrument's unique name.
• The next k lines each contain an integer astronomerId and a string instrument — one completed calibration pass by that astronomer on that instrument. The same (astronomerId, instrument) pair may appear more than once in the log.

Output format

Print exactly n * m lines, one for every (astronomer, instrument) pair, ordered first by ascending astronomer id and then by instrument name in ascending lexicographic (ASCII) order. Each line contains, space-separated: the astronomer's id, the astronomer's name, the instrument's name, and the number of calibration passes that astronomer completed on that instrument (0 if none).

Constraints

• 1 <= n, m <= 200
• 0 <= k <= 5000
• 1 <= id <= 10^6, and all astronomer ids are distinct
• Astronomer names and instrument names are 1 to 20 characters long, consist only of letters and digits, and contain no whitespace
• All instrument names are distinct
• Every astronomerId appearing in the log is one of the n roster ids, and every instrument appearing in the log is one of the m catalogue names

2 2 3
1 Vega
2 Orion
Spectrometer
Photometer
1 Spectrometer
1 Spectrometer
2 Photometer

1 Vega Photometer 0
1 Vega Spectrometer 2
2 Orion Photometer 1
2 Orion Spectrometer 0

1 1 0
5 Lyra
Radar

5 Lyra Radar 0