E. Avalanche
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ piles of stones in a row, numbered from $$$1$$$ to $$$n$$$ from left to right. The $$$i$$$-th pile contains $$$a_i$$$ stones. You are also given an integer $$$k$$$.

Alice and Bob play a game. They take turns, and Alice moves first. In one move, a player chooses a non-empty pile $$$i$$$ and removes one stone from it. Then one new stone is added to each pile $$$j$$$ such that $$$\max(1, i-k) \le j \le i-1$$$, that is, to each of the $$$\min(k, i-1)$$$ piles immediately to the left of pile $$$i$$$. If $$$i = 1$$$, no stones are added. The supply of new stones is unlimited. For example, if $$$i = 5$$$ and $$$k = 2$$$, one stone is added to each of piles $$$3$$$ and $$$4$$$.

The player who cannot make a move loses. It can be shown that the game always ends after a finite number of moves.

Determine the winner if both players play optimally.

Input

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 $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2\cdot 10^5$$$, $$$1 \le k \le n-1$$$) — the number of piles and the parameter of the game.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the numbers of stones in the piles.

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

Output

For each test case, print Alice if Alice wins, and Bob otherwise.

Example
Input
5
2 1
1 1
3 2
0 0 1
4 1
0 0 1 0
5 2
1 2 3 4 5
3 1
2 5 2
Output
Alice
Bob
Alice
Alice
Bob
Note

In the first test case, $$$k = 1$$$ and each of the two piles contains one stone.

  • If Alice takes the stone from the second pile, one stone is added to the first pile, so the piles contain $$$2$$$ and $$$0$$$ stones. Then Bob and Alice take one stone each from the first pile, and Bob cannot move.
  • If Alice takes the stone from the first pile, Bob has to take the stone from the second pile, which adds a stone to the first pile. Alice takes it, and Bob cannot move.

In both cases, Alice wins.

In the second test case, $$$k = 2$$$, and Alice has to take the stone from the third pile. Then one stone is added to each of the first two piles, so the piles contain $$$1$$$, $$$1$$$, and $$$0$$$ stones.

  • If Bob takes the stone from the second pile, a stone is added to the first pile, so the piles contain $$$2$$$, $$$0$$$, and $$$0$$$ stones. Then Alice and Bob take one stone each from the first pile, and Alice cannot move.
  • If Bob takes the stone from the first pile, Alice has to take the stone from the second pile, which adds a stone to the first pile. Bob takes it, and Alice cannot move.

In both cases, Bob wins.