Training Site
Sideways banner

Memory Allocation

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 1 megabytes
Time limit: 0.5 seconds

Techno is creating his own operating system. However, he has encountered a dilemma whilst making his memory allocator.

His computer memory is split into several ranges. Each of these ranges has a type: Free and Used. Techno needs to figure out the next free range past a certain point in memory.

In general:
If a range is of type Free with no overlaps then it is a free range
If a range is of type Used then it is not a free range
If a range has no type then it is of type Used
If a Used range overlaps a Free range then only the non overlapping part is of type Free

It is guaranteed that Free ranges do not overlap themselves and are not directly next to each other. The same holds for Used ranges.


The first line contains the number of free ranges F (0 \leq F \leq 100) and the number of used ranges U (0 \leq U \leq 100)
The following F lines contains the inclusive range start F_s and inclusive range end F_e (0 \leq F_s \leq F_e < 10,000,000)
The following U lines contains the inclusive range start U_s and inclusive range end U_e (0 \leq U_s \leq U_e < 10,000,000)
The following line contains the number of queries Q (0 \leq Q \leq 250,000)
The following Q lines contains a single integer Q_i (0 \leq Q_i < 10,000,000), the point where the next free range needs to be found.


For each query, output on a single line two integers, the inclusive start and end of the next free range.
Note that if a query is within a free range, output the free range the query is in.
If there are no more free ranges then output -1, -1.

Please note the unusually low time and memory limits. This problem may only be fully solvable in C++ or C.


  • Subtask 1 (25%): F_e < 100,000, U_e < 100,000, Q_i < 100,000
  • Subtask 2 (25%): Q \leq 1,000
  • Subtask 3 (25%): Q \leq 100,000
  • Subtask 4 (25%): No other constraints apply.
  • Sample Input 1

    1 2
    100 400
    300 550
    700 900

    Sample Output 1

    100 299
    100 299
    -1 -1
    100 299