P13961 [ICPC 2023 Nanjing R] Grand Finale

In Pigeland, $\textit{Slay the Pig}$ is the most popular roguelike game where players use card decks to challenge a boss called Evil Potato Lord. The general game rules are as follows: - Players start with a set of initial cards in their hand and a draw pile arranged from top to bottom. - At any given time, the player's hand and the draw pile are the only places where cards are present. - Players can play cards from their hands, and each played card will lead to this card being discarded first, and then triggering certain effects. - The player can only use the next card after all the effects of the previously played card have been triggered. In this problem, for simplicity, we will only consider the effect of drawing cards. The rules for drawing cards are as follows: - When using cards that can draw some other cards, players will draw a certain number of cards from the top of the draw pile into their hands in sequential order. - Players have a hand size limit of $k$, and at any given moment, the number of cards in a player's hand cannot exceed the limitation $k$. - When a player attempts to draw a card from the top of the draw pile and their hand already contains $k$ cards, the drawn card will be discarded from the draw pile without triggering any effects and not added to the hand. - When a player attempts to draw a card but the draw pile is empty, nothing will happen. Decks based on the key card $\textit{Grand Finale}$ are the most powerful deck in the game. Once this card is played, it will cause massive damage to all enemies and often leads to victory in the game. However, to play the Grand Finale card, there are strict conditions. That is, the player's draw pile must be empty, which means that all cards must either be played, discarded, or in the player's hand. Bie-Bot is the smartest pig in Pigeland only after the Mysterious Oscar, and he is also playing a $\textit{Grand Finale}$-based deck, which can contain the following four types of cards: :::align{center}  ::: - $\textit{Grand Finale}$: The most powerful card in the game, playing it will lead to an easy victory, and there is exactly one $\textit{Grand Finale}$ in Bie-Bot's deck. This card can only be played if there are no cards in the draw pile. - $\textit{Quick Slash}$: Using this card, you will draw one card from the draw pile. - $\textit{Backflip}$: Using this card, you will draw two cards from the draw pile. - $\textit{Wound}$: A status card that, once it is in your hand, can not be played. At the beginning of the game, Bie-Bot was lucky to have drawn the only one $\textit{Grand Finale}$ in his starting hand, and he also knows that each card in the draw pile from top to bottom. Now, his goal is to successfully play the $\textit{Grand Finale}$ card. Bie-Bot wants to know, under his optimal strategy, what is the minimum hand size limit $k$ required for him to achieve his goal. As the third smartest player in Pigeland, can you help him out? More formally, you are given a string $S_{H}$ of length $n$ representing Bie-Bot's starting hand and a string $S_{P}$ of length $m$ representing the draw pile from top to bottom. Both strings consist of uppercase letters `G`, `Q`, `B` and `W`, indicating that the card at the corresponding position in the starting hand or draw pile is $\textit{Grand Finale}$, $\textit{Quick Slash}$, $\textit{Backflip}$, or $\textit{Wound}$, respectively. Bie-Bot can use the cards in his hand according to the rules mentioned above. Please output the minimum hand size limit $k$ ($k \geq n$) such that Bie-Bot can finally play the $\textit{Grand Finale}$ or state that there is no such $k$.

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 2500$) indicating the number of cards in Bie-Bot's starting hand and draw pile. The second line contains a string $S_{H}$ of length $n$ to represent Bie-Bot's starting hand, consisting of uppercase letters `G`, `Q`, `B`, and `W`. It's guaranteed that there is exactly one `G` in $S_{H}$. The third line of the input contains a string $S_{P}$ of length $m$ to represent Bie-Bot's draw pile from top to bottom, consisting of uppercase letters `Q`, `B`, and `W`. It is guaranteed that the sum of $(n + m)$ of all test cases will not exceed $5 \times 10^4$.

For each test case output one line containing one integer indicating the minimum hand size $k$ ($k \geq n$) that can lead to successfully playing $\textit{Grand Finale}$, or $\texttt{IMPOSSIBLE}$ if it can't be played.

We express the situation with "hand/deck" string. For the first sample test case, one optimal strategy is: - BG/BQWBWW $\overset{B}{\longrightarrow}$ BQG/WBWW - BQG/WBWW $\overset{Q}{\longrightarrow}$ BWG/BWW - BWG/BWW $\overset{B}{\longrightarrow}$ BWG/W (Discard one "W" here due to hand size limit) - BWG/W $\overset{B}{\longrightarrow}$ WWG/$\emptyset$ (Only draw one card here because there is no more card in the draw pile) - WWG/$\emptyset$ $\overset{G}{\longrightarrow}$ Successfully playing $\textit{Grand Finale}$!