题目描述
Jerry Black 有一个长度为 $N$ 的序列 $\{1,2,\cdots,N\}$ 和 $M$ 个区间 $[l_1,r_1],[l_2,r_2],\cdots,[l_M,r_M]$.
现在他可以选择一个正整数 $L$ $(L \ge K)$ 然后将序列划分成 $[1,L],[L+1,2L],\cdots,[tL+1,n]$ 这 $t+1$ 段，其中 $t$ 是满足 $tL+1 \le N$ 的最大非负整数。
例如，在 $N=10,\ K=3$ 时：
- $[1,3],[4,6],[7,9],[10,10]$ 是一种合法的划分方案；
- $[1,3],[4,6],[7,7],[8,10]$ 不是一种合法的划分方案，因为 $[7,7]$ 这一段的长度与此前几段的长度不同，且该段并非是划分后的最后一段；
- $[1,3],[5,7],[8,10]$ 不是一种合法的划分方案，因为 $4$ 未被划分在任何一段内；
- $[1,3],[4,6],[7,10]$ 不是一种合法的划分方案，因为 $[7,10]$ 这一段的长度为 $4$，超过了此前几段的长度 $3$，不满足 $tL+1 \le N$ 条件下 $t$ 的最值性。
定义一个序列为*好序列*，当且仅当**存在至少一种合法的分法** $[L_1,R_1],[L_2,R_2],\cdots,[L_S,R_S]$，并对于任意的 $i \in [1,S]$，都存在 $j \in [1,M]$，使得 $l_j \le L_i \le R_i \le r_j$。换言之，**任何一段**被划分出来的段都应**被完全包含**在**至少一个**区间内。
Jerry Black 想知道他的这个序列是否是一个*好序列*？
输入格式
第一行包含三个正整数 $N,M,K$ $(1 \le K \le N \le 2 \times 10^5,\ 1 \le M \le 2 \times 10^5)$.
接下来 $M$ 行，每行包含两个正整数 $l_i,r_i$ $(1 \le l_i \le r_i \le N)$.