CF2056F2.Xor of Median (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, the constraints on $t$, $k$, and $m$ are higher. You can hack only if you solved all versions of this problem.

A sequence $a$ of $n$ integers is called good if the following condition holds:

• Let $\text{cnt}_x$ be the number of occurrences of $x$ in sequence $a$. For all pairs $0 \le i \lt j \lt m$, at least one of the following has to be true: $\text{cnt}_i = 0$, $\text{cnt}_j = 0$, or $\text{cnt}_i \le \text{cnt}_j$. In other words, if both $i$ and $j$ are present in sequence $a$, then the number of occurrences of $i$ in $a$ is less than or equal to the number of occurrences of $j$ in $a$.

You are given integers $n$ and $m$. Calculate the value of the bitwise XOR of the median$^{\text{∗}}$ of all good sequences $a$ of length $n$ with $0\le a_i \lt m$.

Note that the value of $n$ can be very large, so you are given its binary representation instead.

$^{\text{∗}}$The median of a sequence $a$ of length $n$ is defined as the $\left\lfloor\frac{n + 1}{2}\right\rfloor$-th smallest value in the sequence.

这是该问题的困难版本。两个版本的区别在于，本版本中对 $t$、$k$ 和 $m$ 的约束更强。仅当您已解决该问题的所有版本时，才可进行 hack。

一个由 $n$ 个整数组成的序列 $a$ 被称为好序列，当且仅当满足以下条件：

• 设 $\text{cnt}_x$ 表示 $x$ 在序列 $a$ 中出现的次数。对于所有满足 $0 \le i < j < m$ 的数对 $(i, j)$，下列条件中至少有一个成立：$\text{cnt}_i = 0$、$\text{cnt}_j = 0$ 或 $\text{cnt}_i \le \text{cnt}_j$。换言之，若 $i$ 和 $j$ 均在序列 $a$ 中出现，则 $i$ 在 $a$ 中的出现次数不超过 $j$ 在 $a$ 中的出现次数。

给定整数 $n$ 和 $m$，请计算所有长度为 $n$、且满足 $0 \le a_i < m$ 的好序列 $a$ 的中位数$^{\text{∗}}$ 的异或和（bitwise XOR）。

注意：$n$ 的值可能非常大，因此您将获得其二进制表示形式而非十进制数值。

$^{\text{∗}}$ 序列 $a$（长度为 $n$）的中位数定义为该序列中第 $\left\lfloor\frac{n + 1}{2}\right\rfloor$ 小的值。

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

The first line of each test case contains two integers $k$ and $m$ ($1 \le k \le 2 \cdot 10^5$, $1 \le m \le 10^9$) — the number of bits in $n$ and the upper bound on the elements in sequence $a$.

The second line of each test case contains a binary string of length $k$ — the binary representation of $n$ with no leading zeros.

It is guaranteed that the sum of $k$ over all test cases does not exceed $2\cdot 10^5$.

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

每个测试用例的第一行包含两个整数 $k$ 和 $m$（$1 \le k \le 2 \cdot 10^5$，$1 \le m \le 10^9$）—— 分别表示 $n$ 的二进制位数以及序列 $a$ 中元素的上界。

每个测试用例的第二行包含一个长度为 $k$ 的二进制字符串 —— 即 $n$ 的二进制表示，不含前导零。

保证所有测试用例的 $k$ 值之和不超过 $2\cdot 10^5$。

For each test case, output a single integer representing the bitwise XOR of the median of all good sequences $a$ of length $n$ where $0\le a_i \lt m$.

对于每个测试用例，输出一个整数，表示所有满足条件的序列 $a$（长度为 $n$，且对所有 $i$ 有 $0\le a_i \lt m$）的中位数的按位异或（XOR）结果。

In the first example, $n = 10_2 = 2$ and $m = 3$. All possible sequences with elements less than $m$ are: $[0, 0]$, $[0, 1]$, $[0, 2]$, $[1, 0]$, $[1, 1]$, $[1, 2]$, $[2, 0]$, $[2, 1]$, $[2, 2]$. All of them are good, so the answer is: $0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 2 = 3$.

In the second example, $n = 11_2 = 3$ and $m = 3$. Some good sequences are $[2, 2, 2]$, $[1, 0, 1]$, and $[2, 0, 1]$. However, a sequence $[2, 0, 0]$ is not good, because $\text{cnt}_0 = 2$, $\text{cnt}_2 = 1$. Therefore, if we set $i = 0$ and $j = 2$, $i \lt j$ holds, but $\text{cnt}_i \le \text{cnt}_j$ does not.

在第一个例子中，$n = 10_2 = 2$，$m = 3$。所有元素均小于 $m$ 的可能序列有：$[0, 0]$、$[0, 1]$、$[0, 2]$、$[1, 0]$、$[1, 1]$、$[1, 2]$、$[2, 0]$、$[2, 1]$、$[2, 2]$。它们全都是“好”的序列，因此答案为：$0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 2 = 3$。

在第二个例子中，$n = 11_2 = 3$，$m = 3$。一些“好”的序列包括 $[2, 2, 2]$、$[1, 0, 1]$ 和 $[2, 0, 1]$。然而，序列 $[2, 0, 0]$ 并非“好”的序列，因为 $\text{cnt}_0 = 2$，$\text{cnt}_2 = 1$。因此，若取 $i = 0$ 且 $j = 2$，则 $i \lt j$ 成立，但 $\text{cnt}_i \le \text{cnt}_j$ 不成立。