This is the the hard version. The only defference bewteen this problem and the other problem is the constraint of $$$k$$$. In this problem, $$$1 \lt =k \lt =10^5$$$.
Alice and Bob are playing a new stone game.
There are $$$n$$$ piles of stones in a row, the $$$i$$$-th pile has $$$a_i$$$ stones. They play in turn and Alice goes first. In each turn, the player performs the following operation exactly $$$k$$$ times consecutively:
Remove any number of stones(at least one) from the leftmost pile of stones.
When all stones are removed, the player who will perform the next operation loses, and therefore, their opponent wins. Who will win if they both play optimally?
There are $$$T$$$ test cases.
For each test case, there are two lines.
The first line has two intergers $$$n$$$, $$$k$$$, indicates the number of piles and the number of operations performed by a player consecutively.
The second line has $$$n$$$ intergers, indicates the number of stones of every pile, from left to right.
$$$1 \le T \le 10^5, 1 \le \sum n \le 10^5,1 \le k \le 10^5,1 \le a_i \le 10^9$$$
Out put $$$T$$$ lines. For each test case, output one line 'Alice' or 'Bob', indicates who will win.
32 12 13 23 1 13 21 1 3
Alice Alice Bob
In the second test case of the example, there are three piles of stones, denoted as $$$(3,1,1)$$$. Because $$$k=2$$$, Alice operates twice first, then Bob operates twice, then Alice operates twice again and so on. One possible state changes as follows:
$$$(3,1,1) \mathop{\to}\limits^{Alice} (1,1) \mathop{\to}\limits^{Alice}(1) \mathop{\to}\limits^{Bob} ()$$$
The next operator is Bob and there are no stones. Thus Bob loses.
