F. Front and back stone-taking
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Z-tube Cat invites our old friends Alice and Bob to play their favorite stone-taking game again! This time, the rules for taking stones and generating initial configurations are based on prefixes and suffixes.

In a single game, the configuration consists of a row of $$$m$$$ piles of stones, numbered from $$$1$$$ to $$$m$$$ from front to back. Alice and Bob take turns removing stones, with Alice moving first.

In one turn, the player first chooses two non-negative integers $$$get_{\text{pre}}$$$ and $$$get_{\text{suf}}$$$. Then, they remove one stone from each of the first $$$get_{\text{pre}}$$$ non-empty piles (from the front) and one stone from each of the last $$$get_{\text{suf}}$$$ non-empty piles (from the back). However, at most one stone may be removed from a single pile during the same turn.

The player who, on their turn, removes zero stones loses the game; the other player wins.

Alice and Bob will play $$$n$$$ games. Let $$$a_{i,j}$$$ denote the number of stones in the $$$j$$$-th pile at the beginning of the $$$i$$$-th game. Given two non-negative integers $$$put_{\text{pre}}, put_{\text{suf}}$$$ (with $$$put_{\text{pre}} + put_{\text{suf}} \le m$$$) and the initial configuration of the first game $$$a_{1,1}, \dots, a_{1,m}$$$.

For $$$i \in [2, n]$$$, the initial configuration of the $$$i$$$-th game is generated from that of the $$$(i-1)$$$-th game as follows: take the suffix sums of the first $$$put_{\text{pre}}$$$ piles, take the prefix sums of the last $$$put_{\text{suf}}$$$ piles, and leave the remaining piles unchanged.

More formally,

$$$$$$a_{i,j}=\begin{cases} \sum\limits_{k=j}^{put_{pre}}a_{i-1,k} & j\in[1,put_{pre}] \\ a_{i-1,j} & j\in[put_{pre}+1,m-put_{suf}] \\ \sum\limits_{k=m-put_{suf}+1}^{j}a_{i-1,k} & j\in[m-put_{suf}+1,m] \end{cases}$$$$$$

Both Alice and Bob play optimally. For each of the $$$n$$$ games, determine the winner.

Input

Each test contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), the number of test cases.

For each test case:

The first line contains four integers $$$n, m, put_{\text{pre}}, put_{\text{suf}}$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 10^6$$$, $$$put_{\text{pre}} \ge 0$$$, $$$put_{\text{suf}} \ge 0$$$, $$$put_{\text{pre}} + put_{\text{suf}} \le m$$$), representing the total number of games, the total number of piles in the initial configuration, and the two non-negative integers used to generate the initial configurations, respectively.

The second line contains $$$m$$$ integers $$$a_{1,1}, a_{1,2}, \dots, a_{1,m}$$$ ($$$1 \le a_{1,j} \le 10^9$$$), where $$$a_{1,j}$$$ denotes the number of stones in the $$$j$$$-th pile at the beginning of the first game.

It is guaranteed that, within each test, the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output $$$n$$$ lines, each containing a string.

For the $$$i$$$th line, outputs Alice if Alice wins the $$$i$$$th game; otherwise (if Bob wins the $$$i$$$th game), outputs Bob.

Example
Input
2
3 7 3 2
1 3 1 2 1 2 2
2 6 0 6
7 3 8 3 5 10
Output
Alice
Alice
Bob
Alice
Alice
Note

For the first test case in the sample:

The initial configuration of the first game is $$$1, 3, 1, 2, 1, 2, 2$$$.

Below is a possible gameplay process between Alice and Bob:

  1. Alice chooses $$$get_{\text{pre}} = 4$$$, $$$get_{\text{suf}} = 0$$$, removing $$$4$$$ stones. The configuration becomes $$$0, 2, 0, 1, 1, 2, 2$$$ (i.e., considering only non-empty piles: $$$2, 1, 1, 2, 2$$$).
  2. Bob chooses $$$get_{\text{pre}} = 1$$$, $$$get_{\text{suf}} = 2$$$, removing $$$3$$$ stones. The configuration becomes $$$1, 1, 1, 1, 1$$$.
  3. Alice chooses $$$get_{\text{pre}} = 2$$$, $$$get_{\text{suf}} = 3$$$, removing $$$5$$$ stones. Now all piles become empty.
  4. Bob chooses $$$get_{\text{pre}} = 0$$$, $$$get_{\text{suf}} = 0$$$, removing $$$0$$$ stones. Bob loses this game, and Alice wins.

The initial configuration of the second game is $$$5, 4, 1, 2, 1, 2, 4$$$. The initial configuration of the third game is $$$10, 5, 1, 2, 1, 2, 6$$$.

For the second test case in the sample, the initial configuration of the second game is $$$7, 10, 18, 21, 26, 36$$$.

The input and output for this problem are large. Please use efficient I/O methods.

Finally, Alice and Bob are tired of playing. Let's hope they never play another stone-taking game again…