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 < j < 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 < 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. 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). For each test case, output a single integer representing the bitwise XOR of the median of all good sequences (a) of length (n) wher