CFCF2163D2.Diadrash (Hard Version)

这是本题的 Hard 版本。不同之处在于本题最多可以进行 $30$ 次询问。只有在你已解决所有版本的本题时才能进行 Hack。

本题为交互题。

有一个你未知的排列 $p$，它由 $0$ 到 $n-1$ 的整数构成。此外，给定 $q$ 个区间 $[l_1, r_1], [l_2, r_2], \ldots, [l_q, r_q]$，其中 $1 \le l_i \le r_i \le n$。

你需要找出在输入提供的 $q$ 个区间中，能得到的最大的 $\operatorname{MEX}$ 值。形式化地说，你需要确定 $\max_{i=1}^q{\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])}$ 的值。为此，你最多可以进行 $30$ 次以下形式的询问：

• 任选整数 $1 \le l \le r \le n$，你将会收到 $\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])$ 的值。

$^{\ast}$ 排列是指 $0$ 到 $n-1$ 的整数的一个序列，每个整数恰好出现一次。例如 $[0, 3, 1, 2]$ 是排列，但 $[0, 0, 2, 1]$ 不是。

$^{\dagger}$ 序列的 $\operatorname{MEX}$ 是指序列中没有出现的最小非负整数。例如 $\operatorname{MEX}([0, 0, 1, 3])=2$，$\operatorname{MEX}([1, 2, 2])=0$。

每组测试数据包含多组用例。第一行包含测试用例个数 $t$（$1 \le t \le 100$）。接下来是每组测试用例如下：

每组用例第一行包含两个正整数 $n$ 和 $q$（$4 \le n \le 10^4$，$1 \le q \le 3 \cdot 10^5$），分别表示排列的长度和区间数量。

接下来的 $q$ 行每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$）。

保证所有测试用例中 $n$ 和 $q$ 的总和分别不超过 $10^4$ 和 $3 \cdot 10^5$。

额外约定：同一测试用例中没有重复的区间。

在第一个示例中，隐藏排列为 $p = [0, 3, 1, 2]$，区间为 $[1, 2], [2, 4], [1, 3]$。第 $3$ 个区间最优，因为 $\operatorname{MEX}([p_1, p_2, p_3]) = \operatorname{MEX}([0, 3, 1]) = 2$，为最大值。

第一次询问我们查询 $l=1, r=3$，裁判返回 $\operatorname{MEX}([p_1, p_2, p_3]) = 2$。第二次询问 $l=4, r=4$，裁判返回 $\operatorname{MEX}([p_4]) = 0$。同理，$\operatorname{MEX}([p_1])=1$，$\operatorname{MEX}([p_1, p_2, p_3, p_4])=4$。

最后我们确定答案为 $2$。

第二个示例，$p=[3, 5, 0, 1, 4, 2]$。

第三个示例，$p=[0, 1, 2, 3]$。

注意，这只是对交互方式的说明，并未展示任何解题策略。