Memory Allocation

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.

Input

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.

Output

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.

Subtasks

• 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.