问题 6789 --特工罗宾

6789: 特工罗宾★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 6  解决: 1
[提交][状态][命题人:]

题目描述

特工罗宾因为任务来到A市并在A市停留n天(编号从1n),为此罗宾在A市租了一套豪华的江景房。在此期间,罗宾的哥哥和妈妈要来家中拜访并会在罗宾家中停留连续d天,显然所有这d天必须在第1天到第n天之间(因为n天之后罗宾就退租了哈)。罗宾要为两位来访者选择拜访的日期。

在这n天内,罗宾共计划执行k个危险的任务。第i个任务需要在第li天到第ri天之间完成(li<=ri)。罗宾从小与哥哥一起长大,所以他希望与哥哥共同执行任务。另外,罗宾是一个非常孝顺的孩子,所以他希望尽量能多抽出时间陪陪妈妈。

为此,罗宾希望他哥哥的来访与最多数量的不同任务重叠,而他母亲的来访与最少数量的不同任务重叠。

       请为罗宾的哥哥和母亲的来访找到一个合适的开始日期,使得哥哥来访的d天内罗宾执行最多数量的任务,而妈妈来访的d天内罗宾执行最少数量的任务。如果有多个合适的日子,请选择最早的日期。

输入

第一行一个整数t(1 ≤ t≤1e4):测试样例数;

对于每个测试样例:

第一行三个整数ndk (1≤n≤1e5,1≤d,k≤n):n为罗宾在A市停留的天数,d为两位访客的做客天数,k为罗宾需要执行的任务数;

接下来共k行,每行两个整数,第i行的两个整数为liri1lirin):li为第i个任务的开始日期,ri为第i个任务的结束日期。

输出

      输出共t行,每个测试用例一行两个整数:第1个整数为罗宾为哥哥选择的拜访开始时间,第2个整数是罗宾为妈妈选择的拜访开始时间。     

样例输入
Copy
6
2 1 1
1 2
4 1 2
1 2
2 4
7 2 3
1 2
1 3
6 7
5 1 2
1 2
3 5
9 2 1
2 8
9 2 4
7 9
4 8
1 3
2 3
样例输出
Copy
1 1
2 1
1 4
1 1
1 1
3 4

提示

来源

[提交][状态]