B. Memory Management System
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It is your first day in your new job and guesses what, your first task is already waiting for you! Your task is to build a memory management system.

In this system, the memory will consist of $$$m$$$ bytes ordered from $$$1$$$ to $$$m$$$. Originally, there are $$$n$$$ files in the system, such that the $$$i^{th}$$$ file is occupying all bytes from $$$l_i$$$ to $$$r_i$$$ (inclusive). It is guaranteed that no two files share the same memory position (byte).

The main goal of the system is to answer multiple queries such that each query consists of a file of size $$$k$$$ bytes, and the system must determine if there exist at least $$$k$$$ consecutive bytes that can be reserved and assigned to that file.

Formally, at the $$$j^{th}$$$ query, you are given an integer $$$k_j$$$ and your task is to find a pair of integers $$$l_j$$$ and $$$r_j$$$, such that:

  • All bytes between $$$l_j$$$ and $$$r_j$$$ (inclusive) are free (not occupied).
  • $$$r_j - l_j + 1 \geq k_j$$$.
  • If there are multiple solutions, find the one with the maximum $$$r_j$$$. If there are still multiple solutions, find the one with maximum $$$l_j$$$.
  • If the $$$j^{th}$$$ file cannot be saved in the system, both $$$l_j$$$ and $$$r_j$$$ must be $$$-1$$$.

Please note that you are not reserving the bytes for the files in the queries, you are just checking if there exists an empty space for the file in the system. So, an empty byte in the system can be assigned to multiple queries files. However, if a byte is originally occupied in the system, you cannot use it for the queries files.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10$$$) specifying the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$0 \le n \le m$$$, $$$1 \le m \le 10^5$$$, $$$1 \le q \le \text{min}(10^5, m)$$$), in which $$$n$$$ is the number of files in the system originally, $$$m$$$ is the number of bytes the system contains, and $$$q$$$ is the number of queries.

Then $$$n$$$ lines follow, each line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$), giving the files in system. It is guaranteed that no two files share the same memory position (byte).

Then $$$q$$$ lines follow, each line contains an integer $$$k_j$$$ ($$$1 \le k_j \le m$$$), giving the queries.

Output

For each query $$$j$$$, print two space-separated integers $$$l_j$$$ and $$$r_j$$$, as described in the problem statement. If there are multiple solutions, find the one with the maximum $$$r_j$$$. If there are still multiple solutions, find the one with maximum $$$l_j$$$. If the file cannot be saved in the system, both $$$l_j$$$ and $$$r_j$$$ must be $$$-1$$$.

Example
Input
2
3 9 2
1 1
5 5
8 9
3
2
2 5 3
5 5
1 2
1
2
4
Output
2 4
6 7
4 4
3 4
-1 -1
Note

In the first test case, the memory system can be represented as "OFFFOFFOO", in which 'O' represent an occupied position and 'F' represent a free position.

  • The first file needs to occupy $$$3$$$ bytes. So, the only available answer is $$$2\, 4$$$.
  • The second file needs to occupy 2 bytes. There are $$$3$$$ available intervals, which are: $$$2\, 3$$$, $$$3\, 4$$$, and $$$6\, 7$$$. The interval that satisfies the problem conditions is $$$6\, 7$$$.