Sonar

The Greek Armed Forces, aiming to protect the islands of the eastern Aegean, have developed coastal surveillance systems using sonar since the 1970s. Especially in strategically significant areas, the sonar network was developed in Cartesian form for greater effectiveness. The Information Technology Corps, in collaboration with the Department of Informatics and Telecommunications of the University of Athens, undertook the development of suitable software to provide digital representation of each monitored field. The following diagram illustrates such an example:

The signal level received during the transmission of the emitted sonar is displayed in bold black letters. It is evident that: 1. The signal is of lower level the farther the target is detected. (For an ~N~ by ~N~ sonar system, the closest target to the sonar has a signal level of ~N~, and the most distant target ~1~). 2. When targets move in a line or in a front, the corresponding sonar only receives a signal from the closest target. (In our diagram, the second horizontal sonar only receives the signal from the target with coordinates [~2~, ~4~]).

Note: Targets covered both frontally and in a line, that is, internal targets in a beacon, CANNOT be detected. (Dark area in the following diagram)

Problem:

Develop a program in one of the languages of the IOI that: After reading the non-zero signal levels received by each sonar (first horizontal and then vertical), returns the number of targets that can be detected and their positions sorted by their coordinates (horizontal axis). In our example: [~2~, ~4~], [~2~, ~5~], [~2~, ~6~], [~10~, ~10~]. Note that targets detectable by both horizontal and vertical sonar (e.g., [~2~, ~4~] & [~10~, ~10~]) are "locked" and recorded only once.

Input Files:

The input files named sonar.in are text files with the following structure: The first line contains a number N (~10 \le N \le 99\,999~) indicating the dimensions (~N~ by ~N~) of the monitored field. The second line contains two numbers M1, M2 (separated by a space) indicating the number of horizontal and vertical sonars that detected a target (~M1, M2 \le N^2~). The next ~M1~ lines contain in ascending order the numbers and the corresponding signal level of the horizontal sonars that detected a target. The next ~M2~ lines contain in ascending order the numbers and the corresponding signal level of the vertical sonars that detected a target. In all sonars, their number and the signal level are separated by a space.

Output Files:

The output files named sonar.out are text files with the following structure: The first line contains an integer ~N~ representing the number of detected targets. This is followed by ~N~ lines, each containing the coordinates of the detected targets, sorted by their coordinates. In our example: [~2~, ~4~], [~2~, ~5~], [~2~, ~6~], [~10~, ~10~].

Example of Input - Output File

STDIN (sonar.in)

10
2 4
2 7
10 1
4 9
5 9
6 9
10 1

STDOUT (sonar.out)

4
2 4
2 5
2 6
10 10

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 25 sec.