CF2014D.Robert Hood and Mrs Hood

让你的兄弟印象深刻，但不要让你的母亲烦恼。

Robin 的兄弟和母亲要来拜访，Robin 可以为每位访客选择开始拜访的日期。

所有日期编号为 $1$ 到 $n$。每位访客会连续停留 $d$ 天，这 $d$ 天必须全部在第 $1$ 天到第 $n$ 天之间。

Robin 总共安排了 $k$ 个“风险”工作。第 $i$ 个工作发生在第 $l_i$ 天到第 $r_i$ 天之间（包含两端），其中 $1 \leq i \leq k$。如果某项工作在访客停留的 $d$ 天中的任意一天发生，则认为该工作与此次拜访有重叠（重叠长度无关紧要）。

Robin 希望他的兄弟的拜访与尽可能多的不同工作重叠，而他的母亲的拜访与尽可能少的不同工作重叠。

请为 Robin 的兄弟和母亲分别选择合适的拜访开始日期。如果有多个合适的日期，选择最早的那个。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$d$、$k$（$1 \leq n \leq 10^5, 1 \leq d, k \leq n$），分别表示总天数、每次拜访的持续天数和工作的数量。

接下来每个测试用例有 $k$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），表示每项工作的开始和结束日期。

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

对于每个测试用例，输出两个整数，分别表示 Robin 的兄弟和母亲的最佳拜访开始日期。两次拜访都必须完全在第 $1$ 天到第 $n$ 天之间。

在第一个测试用例中，唯一的工作覆盖了全部 $2$ 天，两人都应在第 $1$ 天拜访。

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

在第三个测试用例中，Robert 拜访的是第 $[1,2]$ 天，Mrs. Hood 拜访的是第 $[4,5]$ 天。

由 ChatGPT 4.1 翻译