CF2163D2.Diadrash (Hard Version)

This is the Hard version of the problem. The difference between the versions is that in this version, you can make at most $30$ queries. You can hack only if you solved all versions of this problem.

This problem is interactive.

There is a permutation$^{\text{∗}}$ $p$ of the integers from $0$ to $n-1$ hidden from you. Additionally, you are given $q$ ranges $[l_1, r_1], [l_2, r_2], \ldots, [l_q, r_q]$ where $1 \le l_i \le r_i \le n$.

You need to discover the maximum $\operatorname{MEX}$ among the values of $p$ in the $q$ ranges that are given to you in the input. Formally, you must discover the value of $\max _{i=1}^q {\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])}$$^{\text{†}}$. To do this, you may make at most $30$ queries of the following form:

• Choose any two integers $1 \le l \le r \le n$ and you will receive the value $\operatorname{MEX}([p_{l}, p_{l+1}, \ldots, p_{r}])$.

$^{\text{∗}}$A permutation of the integers from $0$ to $n-1$ is a sequence of $n$ elements where every integer from $0$ to $n-1$ appears exactly once. For example, the sequence $[0, 3, 1, 2]$ is a permutation, but the sequence $[0, 0, 2, 1]$ is not.

$^{\text{†}}$The $\operatorname{MEX}$ of a sequence is defined as the smallest non-negative integer that does not appear in that sequence. For example, $\operatorname{MEX}([0, 0, 1, 3]) = 2$ and $\operatorname{MEX}([1, 2, 2]) = 0.$

这是本题的困难版本。两个版本的区别在于：在本版本中，你最多可以进行 $30$ 次查询。仅当你解决了本题的所有版本时，才可进行 Hack。

本题为交互式问题。

存在一个隐藏的排列$^{\text{∗}}$ $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$ 个区间中，对应子数组 $p$ 的值所构成序列的最大 $\operatorname{MEX}$。形式化地，你需要求出 $\max _{i=1}^q {\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])}$$^{\text{†}}$。为此，你最多可进行 $30$ 次如下形式的查询：

• 任选两个整数 $1 \le l \le r \le n$，系统将返回 $\operatorname{MEX}([p_{l}, p_{l+1}, \ldots, p_{r}])$ 的值。

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

$^{\text{†}}$一个序列的 $\operatorname{MEX}$ 定义为该序列中未出现的最小非负整数。例如，$\operatorname{MEX}([0, 0, 1, 3]) = 2$，而 $\operatorname{MEX}([1, 2, 2]) = 0$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains exactly two integers $n$ and $q$ ($4 \le n \le 10^4$, $1 \le q \le 3 \cdot 10^5$) — the size of the permutation and the number of ranges, respectively.

The $i$-th of the next $q$ lines contains two integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$).

It is guaranteed that the sum of $n$ and $q$ do not exceed $10^4$ and $3 \cdot 10^5$ respectively over all test cases.

Additional Constraint: it is guaranteed that no range is repeated in the same test case.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

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

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

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

附加约束：保证在同一测试用例中，没有重复的区间。

In the first example, the hidden permutation is $p = [0, 3, 1, 2]$ and the ranges are $[1, 2], [2, 4], [1, 3]$. The third range is optimal, as $\operatorname{MEX}([p_1, p_2, p_3]) = \operatorname{MEX}([0, 3, 1]) = 2$, which is maximum.

In our first query, we ask about $l = 1, r = 3$ and the judge gives us the value $\operatorname{MEX}([p_1, p_2, p_3]) = 2$. In the second query, we ask about $l = 4, r = 4$ and the judge gives us the value $\operatorname{MEX}([p_4]) = 0$. Likewise, $\operatorname{MEX}([p_1]) = 1$ and $\operatorname{MEX}([p_1, p_2, p_3, p_4]) = 4$.

Somehow, we figure out that the answer we are looking for is $2$.

In the second example, $p = [3, 5, 0, 1, 4, 2]$.

In the third example, $p = [0, 1, 2, 3]$.

Note that this is just an explanation of the way the interaction works and does not show any strategy to solve the problem.

在第一个例子中，隐藏的排列为 $p = [0, 3, 1, 2]$，查询区间为 $[1, 2], [2, 4], [1, 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]$。

注意：这仅是对交互机制的说明，并未展示任何解决该问题的策略。