Training Site
Sideways banner

Memory Allocation

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 1 megabytes
Time limit: 1.0 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 <= F <= 100) and the number of used ranges U (0 <= U <= 100)
The following F lines contains the inclusive range start F_s and the range end F_e (0 <= F_s < F_e < 10,000,000)
The following U lines contains the inclusive range start U_s and the range end U_e (0 <= U_s < U_e < 10,000,000)
The following line contains the number of queries Q (0 <= Q <= 100,000)
The following Q lines contains a single integer, 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


  • Subtask 1 (25%): F_e < 100,000, U_e < 100,000
  • Subtask 2 (25%): Q <= 100
  • Subtask 3 (50%): 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