题目描述

There are $N$ stones in a row, and each stone is colored either white or black.

Alice and Bob play the following game using these stones:

• The players alternate turns, and Alice goes first.
• On each turn, the current player must remove exactly one stone from either the left or right end.
• If the total number of black stones removed by the two players reaches $M$, the player who makes that move loses, and the other player wins.

Determine which player will win the game when both players play optimally. It is guaranteed that the number of black stones is at least $M$.

输入格式

The input consists of multiple test cases.

The first line contains an integer $T$ ($1 \leq T \leq 1000$), representing the number of test cases.

$T$ test cases follow. Each test case is given in the following format.

For each test case, the first line contains integers $N$ ($1 \leq N \leq 500\,000$) and $M$ ($1 \leq M \leq N$), representing the total number of stones and the losing threshold, respectively.

The next line contains a string $S$ of length $N$, consisting only of 'B' and 'W'. The $i$-th character of $S$ represents the color of the $i$-th stone from the left: it is 'B' if the stone is black, and 'W' if the stone is white. It is guaranteed that the number of black stones is at least $M$.

It is guaranteed that the sum of $N$ over all test cases does not exceed $500\,000$.

输出格式

For the $T$ test cases, output the answers separated by newlines. For each test case, output the name of the player who will win.

3
5 1
WBBWB
5 2
WBBWB
5 3
WBBWB

Alice
Alice
Bob

提示

In the first test case, if Alice removes the leftmost white stone, the remaining stones are “BBWB”. No matter which side Bob chooses from, he will end up picking a black stone, so Bob loses.

In the second test case, Alice will win. For example, the game could proceed as follows:

1. Alice removes the black stone from the rightmost position.
2. Bob removes the white stone from the rightmost position.
3. Alice removes the white stone from the leftmost position.
4. Bob removes the black stone from the rightmost position.