询问 $m=0,v=i$ 可以确定端点是否是 $i$，于是 $n-O(1)$ 次操作得到一个端点。得到一个端点后，使用交互题常见思路直接二分逐个确定后面的元素。但是询问好奇怪！怎么二分？

如果我们可以自己决定 $S$ 具体是什么，那么就直接普通二分。当前上一个确定的元素是 $x$，如果 $[l,r]$ 中有元素和 $x$ 相邻，那么 $c([l,r]\cup x)-c([l,r])$ 为某个特殊值（特殊值取决于 $x$ 是不是 $p_0$，如果是，这个值就是 $-1$；如果不是，这个值就是 $0$）。

不能自己决定 $S$ 是什么太坏了，这个 popcount 有什么可以二分的吗？我最开始的思路是直接只询问 $m=2^v-1$ 的数，可以得到二进制中某个前缀中 $1$ 个数为奇数的数是否与 $S$ 相邻。实际上麻烦了。我们直接只询问 $m=2^v$，这样就可以让 $S$ 变成某个二进制位为 $1$ 的数的集合，然后你 $\log n$ 次查询就可以得到下一个元素的每个二进制位是什么了。一样是看 $c(B(2^v)\cup x)-c(B(2^v)-\{x\})$ 的值是不是某个特殊值，这个特殊值取决于 $x$ 是不是 $p_0$，以及 $x$ 的上一个元素 $y$ 是否也在 $B(v)$ 中。

当前做到的复杂度是 $n+2nk$。但是我们发现实际上我们的询问都是重复的。提前问好即可，我们只会询问 $(0,i)$（$i\in[1,n]$），与 $(2^v,i)$，其中 $i\in[-1,n-1]$，那么复杂度就变成了 $n+(n+1)k$。

然后我们发现我们其实只用确定排列前 $n-1$ 个元素，最后一个元素自然出来了，于是对于 $2^v$ 的询问，$i$ 会相比之前少问一个终点。复杂度 $n+nk$。

呃啊，是不是找到一个端点太难了？能不能不特别去询问 $m=0$，而是用 $m=2^v$ 的询问得到这个端点？

对于两个不同的数 $x,y$，其总有一二进制位满足 $x$ 在这一位和 $y$ 这一位不同。

这等价于：

对于三个不同的数 $p_{i-1},p_i,p_{i+1}$，有一个二进制位满足三个数在这个二进制位为以下情况之一：

• $0,0,1$
• $0,1,1$
• $1,0,0$
• $1,1,0$

怎么 check 一个位是否是端点？我们考虑询问 $(2^v,i)$。如果 $v$ 恰好就是满足 $p_{i-1}$ 和 $p_{i+1}$ 在这个二进制位不同的一个 $v$。那么必然有 $c(B(2^v)\cup x)-c(B(2^v)-\{x\})=0$，尝试画画看来理解吧（提示：因为只有一边是 $1$，所以把 $p_i$ 补上、或者删掉之后，这个值不会变化）。

如果不满足，上面这个差必然不为 $0$。

所以只需要对于每个 $i$，枚举 $v$，如果存在一个 $v$ 使得差为 $0$，说明 $i$ 不是端点。否则 $i$ 必然是端点。显然我们只会找 $n-1$ 次就会找到一个端点，然后剩下那一个必然是终点。我们也刚好不会不小心多问到终点。

那么对于每个 $v$，我们只会问 $(2^v,i)$，其中 $i$ 是 $[-1,n-1]$ 去掉一个终点

此时询问次数就变成了 $nk$，非常美丽！