罗宾的兄弟和母亲来访,罗宾可以为每位访客选择开始日期。
所有日期的编号从 $$$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]$$$ 天。