The Z-shaped pipe cat invites our old friends Alice and Bob to play their favorite stone-taking game. This time, the game is based on prefix/suffix stone-taking rules and an initial state generation rule.
In a single game, the state consists of a row of $m$ piles of stones, from the 1st pile to the $m$-th pile. Alice and Bob take turns taking stones. Alice goes first.
In a turn, the current player first chooses two non-negative integers $get_{pre}$ and $get_{suf}$, then takes 1 stone from each of the first $get_{pre}$ piles that contain stones, and 1 stone from each of the last $get_{suf}$ piles that contain stones. However, in the same turn, at most 1 stone can be taken from any single pile.
The first player who takes 0 stones in their turn loses the game, and 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 in the initial state of the $i$-th game. Given two non-negative integers $put_{pre}$ and $put_{suf}$ ($put_{pre} + put_{suf} \le m$) and the initial state of the 1st game $a_{1,1}, \dots, a_{1,m}$.
The generation rule for the initial state of the $i$-th game ($i \in [2, n]$) is: first, based on the initial state of the $(i-1)$-th game, take the suffix sum of the stone counts for the first $put_{pre}$ piles, and take the prefix sum of the stone counts for the last $put_{suf}$ piles, while the remaining parts remain unchanged.
More formally:
$$ a_{i,j} = \begin{cases} \sum_{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_{k=m-put_{suf}+1}^{j} a_{i-1,k} & j \in [m - put_{suf} + 1, m] \end{cases} $$
Alice and Bob both use optimal strategies. Please determine the winner of each of the $n$ games.
Input
Each test case contains multiple test data. The first line gives an integer $T$ ($1 \le T \le 10^4$), representing the number of test data groups.
For each test data group: The first line gives four integers $n, m, put_{pre}, put_{suf}$ ($1 \le n \le 10^6, 1 \le m \le 10^6, put_{pre} \ge 0, put_{suf} \ge 0, put_{pre} + put_{suf} \le m$), representing the total number of games, the total number of stone piles in the initial state, and the two non-negative integers for generating the initial state, respectively. The second line gives $m$ integers $a_{1,j}$ ($1 \le a_{1,j} \le 10^9$), where the $j$-th integer $a_{1,j}$ represents the number of stones in the $j$-th pile in the initial state of the 1st game.
It is guaranteed that in each test point, the sum of $n$ over all test data does not exceed $10^6$, and the sum of $m$ does not exceed $10^6$.
Output
For each test data group, output $n$ lines, each containing a string. For the $i$-th line, if Alice wins the $i$-th game, output Alice; otherwise (if Bob wins the $i$-th game), output Bob.
Examples
Input 1
2 3 7 3 2 1 3 1 2 1 2 2 2 6 0 6 7 3 8 3 5 10
Output 1
Alice Alice Bob Alice Alice
Note
For the first test data of the example: The initial state of the 1st game is 1, 3, 1, 2, 1, 2, 2. Below is a possible game process for Alice and Bob:
- Alice chooses $get_{pre} = 4, get_{suf} = 0$, takes 4 stones, the state becomes 0, 2, 0, 1, 1, 2, 2, i.e., (keeping only piles with stones) 2, 1, 1, 2, 2.
- Bob chooses $get_{pre} = 1, get_{suf} = 2$, takes 3 stones, the state becomes 1, 1, 1, 1, 1.
- Alice chooses $get_{pre} = 2, get_{suf} = 3$, takes 5 stones, at this point all piles have no stones.
- Bob chooses $get_{pre} = 0, get_{suf} = 0$, takes 0 stones. Bob loses the game, Alice wins.
The initial state of the 2nd game is 5, 4, 1, 2, 1, 2, 4. The initial state of the 3rd game is 10, 5, 1, 2, 1, 2, 6.
For the second test data of the example, the initial state of the 2nd game is 7, 10, 18, 21, 26, 36.
The input and output volume of this problem is large, please pay attention to the input and output methods used.
Finally, Alice and Bob are exhausted, hoping they never play stone-taking games again...