A16671 | 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$。

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