CF2135D2.From the Unknown (Hard Version)

这是该问题的高难度版本。两种版本的区别在于，在本版本中，所有询问中所有文章的长度之和不得超过 $2.5\cdot 10^4$。你只有在解决了该问题的所有版本后才能进行 hack。

这是一个交互题。

RiOI 团队最近开发了一个名为 RiOI Editor 的文本编辑器。该编辑器只有一个整数参数 $W$ —— 每行的宽度。已知 $1 \leq W \leq 10^5$。

由于你无法理解 RiOI 语言，在你看来，单词之间唯一的区别就是它们的长度。因此，长度为 $n$ 的一篇文章被定义为一个长度为 $n$ 的序列 $a$，其中 $a_i$ 表示第 $i$ 个单词的长度。RiOI 编辑器显示文章 $[a_1, a_2,\ldots, a_n]$ 的方式如下：

• 如果 $\max(a_1, a_2, \ldots, a_n)\gt W$，编辑器无法显示该文章；
• 否则，编辑器能通过以下过程显示该文章：
  • 初始时 $l = 1$，$s = 0$。在整个过程中，$l$ 始终表示当前的行数，$s$ 始终表示当前最后一行的单词长度之和；
  • 然后，对于每个 $1\le i\le n$：
    • 如果 $s + a_i \leq W$，则将该单词插入当前行末，$l$ 不变，$s$ 增加 $a_i$；
    • 否则，将该单词插入新的一行，$l$ 增加 $1$，$s$ 变为 $a_i$。
  • 显示这篇文章所需的行数即为最终的 $l$。

你对该编辑器很感兴趣，因此你决定通过向编辑器输入一些文章，并观察显示该文章所需行数，来推测 $W$ 的值。

具体来说，你最多可以询问评测机 $2$ 次。每次询问时，你向编辑器输入一篇文章 $[a_1, a_2, \ldots, a_n]$（$1\leq n \leq 10^5$），编辑器将回复：

• 如果编辑器可以正常显示该文章，则返回显示此文章所需的行数；
• 如果编辑器无法显示，则返回 $0$。

本版本的额外限制：所有询问中文章的总长度（即 $n$ 的总和）不得超过 $2.5\cdot 10^4$。

每组测试数据包含多个测试用例。首行为测试用例数 $t$（$1 \le t \le 10$）。接下来是每个测试用例的描述。

（交互题，无输出格式，详见题面）

在第一个测试用例中：

• 第一次询问，所有单词的总长度为 $1+9+4+6+1=21$，文章被分为两行显示，所以 $W\lt21$；
• 第二次询问，所有单词长度为 $10+10=20$，文章仅用一行显示，所以 $W\ge 20$。

由此可确定 $W = 20$。

在第二个测试用例中，只有一次询问，并且编辑器无法显示该文章。因此 $W\lt 2$，所以只能是 $1$。

由 ChatGPT 5 翻译