CF1290D.Coffee Varieties (hard version)

This is the hard version of the problem. You can find the easy version in the Div. 2 contest. Both versions only differ in the number of times you can ask your friend to taste coffee.

This is an interactive problem.

You're considering moving to another city, where one of your friends already lives. There are $n$ cafés in this city, where $n$ is a power of two. The $i$-th café produces a single variety of coffee $a_i$.

As you're a coffee-lover, before deciding to move or not, you want to know the number $d$ of distinct varieties of coffees produced in this city.

You don't know the values $a_1, \ldots, a_n$. Fortunately, your friend has a memory of size $k$, where $k$ is a power of two.

Once per day, you can ask him to taste a cup of coffee produced by the café $c$, and he will tell you if he tasted a similar coffee during the last $k$ days.

You can also ask him to take a medication that will reset his memory. He will forget all previous cups of coffee tasted. You can reset his memory at most $30\ 000$ times.

More formally, the memory of your friend is a queue $S$. Doing a query on café $c$ will:

• Tell you if $a_c$ is in $S$;
• Add $a_c$ at the back of $S$;
• If $|S| \gt k$, pop the front element of $S$.

Doing a reset request will pop all elements out of $S$.

Your friend can taste at most $\dfrac{3n^2}{2k}$ cups of coffee in total. Find the diversity $d$ (number of distinct values in the array $a$).

Note that asking your friend to reset his memory does not count towards the number of times you ask your friend to taste a cup of coffee.

In some test cases the behavior of the interactor is adaptive. It means that the array $a$ may be not fixed before the start of the interaction and may depend on your queries. It is guaranteed that at any moment of the interaction, there is at least one array $a$ consistent with all the answers given so far.

这是该问题的困难版本。你可以在 Div. 2 比赛中找到简单版本。两个版本的唯一区别在于你向朋友请求品尝咖啡的次数限制。

这是一个交互式问题。

你正考虑搬到另一座城市，而你的一个朋友已经居住在那里。这座城市共有 $n$ 家咖啡馆，其中 $n$ 是 2 的幂。第 $i$ 家咖啡馆生产一种特定的咖啡 $a_i$。

作为一名咖啡爱好者，在决定是否搬去之前，你想知道这座城市所生产的咖啡品种数 $d$（即数组 $a$ 中不同值的个数）。

你并不知道 $a_1, \ldots, a_n$ 的具体取值。幸运的是，你的朋友拥有容量为 $k$ 的记忆，其中 $k$ 也是 2 的幂。

每天最多可向他提出一次请求：请他品尝由咖啡馆 $c$ 所生产的咖啡一杯；他将告诉你，在最近 $k$ 天内他是否曾品尝过相同品种的咖啡。

你还可以请求他服用一种药物以重置其记忆——这会使他遗忘此前所有品尝过的咖啡。你最多可重置其记忆 $30\,000$ 次。

更形式化地说，你朋友的记忆是一个队列 $S$。对咖啡馆 $c$ 发起一次查询将：

• 告知你 $a_c$ 是否在 $S$ 中；
• 将 $a_c$ 添加至 $S$ 队尾；
• 若 $|S| > k$，则从 $S$ 队首弹出一个元素。

发起一次重置请求将清空 $S$ 中所有元素。

你的朋友总共最多品尝 $\dfrac{3n^2}{2k}$ 杯咖啡。请确定多样性 $d$（即数组 $a$ 中不同值的个数）。

注意：请求朋友重置记忆不计入你请求他品尝咖啡的总次数。

在部分测试用例中，交互器的行为是自适应的。这意味着数组 $a$ 在交互开始前未必已固定，其取值可能依赖于你所发出的查询。但可以保证：在交互过程中的任意时刻，都至少存在一个数组 $a$，与迄今为止所有已给出的回答一致。

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 1024$, $k$ and $n$ are powers of two).

It is guaranteed that $\dfrac{3n^2}{2k} \le 15\ 000$.

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 1024$，且 $n$ 和 $k$ 均为 $2$ 的幂）。

保证 $\dfrac{3n^2}{2k} \le 15\ 000$。

In the first example, the array is $a = [1, 4, 1, 3]$. The city produces $3$ different varieties of coffee ($1$, $3$ and $4$).

The successive varieties of coffee tasted by your friend are $1, 4, \textbf{1}, 3, 3, 1, 4$ (bold answers correspond to Y answers). Note that between the two ? 4 asks, there is a reset memory request R, so the answer to the second ? 4 ask is N. Had there been no reset memory request, the answer to the second ? 4 ask is Y.

In the second example, the array is $a = [1, 2, 3, 4, 5, 6, 6, 6]$. The city produces $6$ different varieties of coffee.

The successive varieties of coffee tasted by your friend are $2, 6, 4, 5, \textbf{2}, \textbf{5}$.

在第一个例子中，数组为 $a = [1, 4, 1, 3]$。该城市生产 $3$ 种不同的咖啡（即品种 $1$、$3$ 和 $4$）。

你的朋友依次品尝的咖啡品种为 $1, 4, \textbf{1}, 3, 3, 1, 4$（加粗的答案对应于回答 Y）。注意：在两次询问 ? 4 之间存在一次重置记忆请求 R，因此第二次 ? 4 询问的回答为 N。若中间没有重置记忆请求，则第二次 ? 4 询问的回答应为 Y。

在第二个例子中，数组为 $a = [1, 2, 3, 4, 5, 6, 6, 6]$。该城市生产 $6$ 种不同的咖啡。

你的朋友依次品尝的咖啡品种为 $2, 6, 4, 5, \textbf{2}, \textbf{5}$。