CATINV - Cats Invitation


In Kutus and Putus' first marriage anniversary, they planned to invite all of their cat friends. So they invited all cats in a hall room. Due to business, all of the cats couldn't attend the party at the same time. Different cats attended party at different times and some of them couldn't stay till the end. Kutus wanted to make Putus as much happy as possible. If at any moment, there were 'L' cats present in the hall room, then happiness level of Putus were 'L' at that moment. Now Kutus gave you a list of every cats' arrival and departure time at the party and asked you few queries: Maximum time segment where the happiness level of Putus was 'L'.

Input

Input starts with an integer T, which denotes the number of test cases. Each case contains 2 space separated integer N and Q denoting the number of cats came to the party and the number of queries to be performed. Next N lines contains space separated integers 'X' and 'Y' denoting the arrival time and departure time of ith cat. Each of the next Q lines contains an integer 'L' as described above.

Output

For each case print the case number and print the time segment 'X' and 'Y' that is Putus' level of happiness. If there are multiple solution, print the time segment that comes earliest. If there is no possible answer, print -1.

Constraints

T <= 10

1 <= N <= 100000

1 <= Q <= 100000

1 <= Xi <= Yi <= 100000

1 <= L <= 100000

Example

Input:
1
5 5
1 2
2 3
1 3
2 4
3 5
1
2
3
4
5

Output:
Case 1:
4 4
1 1
2 2
-1
-1

hide comments
Simes: 2018-12-21 21:41:23

"Next line contains N space separated integers..." not according to the example it doesn't.
[Simes]: corrected.

Last edit: 2023-01-25 16:07:52
Sigma Kappa: 2017-08-28 22:37:38

If X == Y, i.e. the cat departs at the moment it arrives, we can ignore it, right?

EDIT: No, don't ignore it; and such cases do occur in the test data. Just got Accepted by O(nlogn + q)

Last edit: 2017-08-29 02:09:01
geeta: 2017-07-14 11:18:21

O(n+q) gives tle -_-

hodobox: 2017-03-06 20:20:13

O(N+Q) worked for me.

Last edit: 2017-03-06 20:20:47
chiragm23: 2016-09-18 17:00:53

I have implemented O(n) solution but still getting TLE.
Admin plz check my solution id 17736800 and give me some suggestions.
Thank you..!!

Jobayer_sheikh: 2016-09-09 22:29:30

Nice problem, O(n) works fine


Added by:Anick
Date:2016-08-26
Time limit:0.400s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU