A81873.参观博物馆

博物馆在接下来的 $n$ 天中举办了 $k$ 场展览，第 $i$ 场展览在第 $l_i$ 到 $r_i$ 天之间展出（包含两端）。

现在有一位摄影师和一位评论家要参观博物馆，每人参观 $d$ 天，且起始日期必须在 $1$ 到 $n−d+1 $ 之间。

• 摄影师希望他的参观期尽可能多地举办不同展览（即参观区间与尽可能多的展览重叠）；

• 评论家希望她的参观期尽可能避开展览（重叠数量最少）。

为两人参观寻找合适的起始日期，如有多个满足要求的起始日期，选择最早的那个。

• 第一行：三个整数 $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)$。

输出两个整数，分别表示摄影师和评论家的最佳起始日期。注意，这俩人的的参观日期必须都在 $1$ 和 $n$ 之间。

• 在第一个测试样例中，可以发现摄影师能遇到最多两个不同展览，在参观日期区间为 $[1,2]$ 时有两个不同展览，且起始日期 $1$ 最早，评论家在区间 $[4,5]$ 时参观可以避开所有展览。

• 对于 $40\%$ 的数据，$1\le n \le 5000$。

• 对于另外 $60\%$ 的数据，$n \ge 10000$。

• 对于 $100\%$ 的数据，$1\le n \le 10^5,1\le d,k \le n,1 \le l_i \le r_i \le n$。