AT_arc164_e.[ARC164E] Segment-Tree Optimization

有一个长度为 $N$ 的序列，$Q$ 次询问，每一次询问会覆盖到一个区间 $[L,R]$。

你需要构造一个二叉树，满足以下条件：

• 每个节点对应一个区间
• 根节点对应区间 $[1,N]$
• 叶子节点对应区间 $[i,i]$，同时对应区间 $[i,i]$ 的节点一定是叶子节点
• 每一个非叶子节点一定有两个子节点，如果一个非叶子节点对应 $[i,j]$，那么它的两个子节点对应区间分别为 $[i,k],[k+1,j](i \le k < j)$

对区间 $[L,R]$ 进行一次询问时，从根节点开始搜索，如果一个节点对应的区间被完全包含在 $[L,R]$ 中或该节点对应的区间与 $[L,R]$ 没有重叠，则不遍历其子节点，否则遍历其所有子节点。

记 $d$ 为遍历到的节点的最大深度，$c$ 为深度为 $d$ 的节点被遍历到的总次数，你需要在保证在 $d$ 最小的条件下 $c$ 最小，输出 $d$ 和 $c$。

translated by @lelml

第一行两个整数 $N,Q$。

之后 $Q$ 行，每一行两个数 $L_i,R_i$，表示一次询问。

一行两个数 $d,c$，表示答案。

$2 \le N \le 4000,1 \le Q \le 10^5,1 \le L_i \le R_i \le N(1\le i \le Q)$