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

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

Subtasks

• Subtask 1 (25%): $F_e < 100,000$, $U_e < 100,000$
• Subtask 2 (25%): $Q <= 100$
• Subtask 3 (50%): No other constraints apply.