← 返回题目列表

Codeforces · 2014/D

D. 罗伯特·胡德和胡德夫人

中文机器翻译题面 查看原题

罗宾的兄弟和母亲来访,罗宾可以为每位访客选择开始日期。

所有日期的编号从 $$$1$$$ 到 $$$n$$$。访客连续停留 $$$d$$$ 天,所有这些 $$$d$$$ 天必须在 $$$1$$$ 和 $$$n$$$ 之间(含)。

Robin 计划了总共 $$$k$$$ 有风险的“工作”。第 $$$i$$$ 作业发生在 $$$l_i$$$ 和 $$$r_i$$$ 之间(包括 $$$1 \le i \le k$$$)。如果某项工作发生在 $$$d$$$ 日中的任何一天,则访问与该工作重叠(重叠的时间长短并不重要)。

Robin 希望他哥哥的来访与最大数量的不同工作重叠,而他的母亲是最少的。

为罗宾的兄弟和母亲的探访找到合适的开始日期。如果有多个合适的日子,请选择最早的一个。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行由三个整数组成 $$$n$$$、$$$d$$$、$$$k$$$ ($$$1 \le n \le 10^5, 1 \le d, k \le n$$$) — 总天数、访问持续时间和作业数量。

然后跟踪每个测试用例的 $$$k$$$ 行,每行都有两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) - 每个作业的开始和结束日期。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出两个整数,分别是Robin的哥哥和母亲的最佳开始天数。两次访问必须在 $$$1$$$ 和 $$$n$$$ 之间(含)。

示例

输入 #1

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

输出 #1

1 1
2 1
1 4
1 1
1 1
3 4

注意

在第一个测试用例中,唯一的作业填满了所有 $$$2$$$ 天,两者都应该在 $$$1$$$ 天访问。

在第二个测试用例中,$$$2$$$ 天与 $$$2$$$ 工作重叠,$$$1$$$ 天仅与 $$$1$$$ 重叠。

在第三个测试用例中,罗伯特访问了 $$$[1,2]$$$ 天,胡德夫人访问了 $$$[4,5]$$$ 天。