410574: GYM104053 H GameX

Once upon a time, there were two saints named St. Alice and St. Bob.

Being saints were quite boring, so they decided to play a game. The game was about the MEX operation, and was therefore named GameX.

To help you, a mere mortal, to understand the game, we first present the definition of MEX. Given a set $$$S$$$ of integers, define $$$\text{MEX}(S)$$$ as the smallest natural number which is not in $$$S$$$. In other words, $$$\text{MEX}(S)=\min\{x\in \mathbb{N}\mid x\not \in S\}$$$.

The game went as follows.

Before the game started, $$$S=\{a_1,a_2,\cdots,a_n\}$$$, which contained the Secret of Life, the Universe and Everything.

The two saints moved alternately, with St. Alice being the first. During one's move, he/she could choose an arbitrary integer $$$x$$$, and insert $$$x$$$ into $$$S$$$. So $$$S$$$ is updated to $$$S\cup \{x\}$$$.

After $$$k$$$ rounds, each player made $$$k$$$ updates, and now it's time to decide the winner. St. Alice wins iff $$$\text{MEX}(S)$$$ is even, and Bob wins otherwise.

Saints are very smart, so both of them made optimal moves. Can a mortal like you decide the winner?

The first line contains a positive integer $$$T$$$ ($$$1\le T\le 10^4$$$), denoting the number of testcases.

For each testcase:

• The first line contains two integers $$$n, k$$$ ($$$1\le n,k\le 2\times 10^5$$$), denoting the size of $$$S$$$ before the game started and the number of rounds.
• The next line contains $$$n$$$ distinct natural numbers $$$a_1,a_2,\cdots,a_n$$$ ($$$0\le a_i\le 10^6$$$), denoting $$$S$$$.

It is guaranteed that $$$\sum n, \sum k\le 2\times 10^5$$$.

For each testcase, output one line consisting of the name of the winner. If St. Alice won output Alice, otherwise output Bob.

5
14 5
7 13 1 6 14 2 16 17 18 19 34 36 20 23
13 5
8 10 3 13 14 15 16 17 18 19 20 36 38
14 5
14 20 12 6 0 16 8 11 9 17 13 3 5 19
14 5
15 7 13 3 1 17 16 14 0 12 4 10 22 53
14 5
7 3 4 0 14 15 16 17 18 19 20 21 22 23

Bob
Bob
Alice
Bob
Alice