#P18446. Grand Finale

Grand Finale

Grand Finale

输入:标准输入;输出:标准输出。

在 Pigeland,Slay the Pig 是最受欢迎的 Roguelike 游戏,玩家使用卡牌挑战名为 Evil Potato Lord 的首领。

一般游戏规则如下:

  1. 玩家开始时有一些初始手牌,以及一个从顶到底排列的抽牌堆。
  2. 任意时刻,卡牌只可能位于手牌或抽牌堆中。
  3. 玩家可以打出手牌中的牌;每次打出时,先弃掉这张被打出的牌,再结算它的效果。
  4. 只有当前这张牌的所有效果都结算完毕后,才能打出下一张牌。

本题只考虑抽牌效果,抽牌规则如下:

  1. 打出能抽牌的卡牌后,按照牌堆从顶到底的顺序,逐张尝试把指定数量的牌抽入手牌。
  2. 手牌数量上限为 kk,任意时刻都不能超过 kk。
  3. 如果尝试抽取牌堆顶的牌时,手牌已有 kk 张,那么这张被抽到的牌直接从牌堆中弃掉,不进入手牌,也不触发任何效果。
  4. 如果抽牌堆已经为空,那么这一次抽牌不产生任何效果。

以 Grand Finale 为核心的牌组十分强大,打出这张牌会对所有敌人造成大量伤害,通常能带来胜利。但它有一个严格的出牌条件:抽牌堆必须为空。

Bie-Bot 的牌组只含以下四类卡牌:

字符 卡牌 本题中的效果或条件
G Grand Finale 仅当抽牌堆为空时才能打出;整个牌组中恰好有一张
Q Quick Slash 抽一张牌
B Backflip 按顺序抽两张牌
W Wound 一旦进入手牌,就不能被打出

原题四种牌的示意图如下。本题采用上述简化规则,仅考虑抽牌,不引入图片中的伤害、格挡或费用机制。

原题的 Grand Finale、Quick Slash、Backflip、Wound 四种卡牌

Bie-Bot 幸运地在初始手牌中抽到了唯一的 G,并且知道整个抽牌堆从顶到底的顺序。他希望最终能打出 G。

给定长度为 nn 的字符串 SHS_H 表示初始手牌,长度为 mm 的字符串 SPS_P 表示牌堆从顶到底的顺序。SHS_H 由 GQBW 构成且恰有一个 G;SPS_P 仅由 QBW 构成。可以在任意时刻选择手中可打出的牌,按最优策略行动。

求能够成功的最小手牌上限 kk,要求 k≥nk\ge n。如果不存在这样的上限,则报告无法成功。

输入格式

第一行包含整数 TT,表示测试用例数。

对于每个测试用例:

第一行包含两个整数 n,mn,m(1≤n,m≤25001\le n,m\le2500)。

第二行包含长度为 nn 的字符串 SHS_H,仅含大写字母 G、Q、B、W,且恰好含有一个 G。

第三行包含长度为 mm 的字符串 SPS_P,仅含大写字母 Q、B、W。

保证一个输入文件内,所有测试用例的 n+mn+m 之和不超过 5×1045\times10^4。

输出格式

对每个测试用例输出一行:

  • 如果可以成功,输出能够最终打出 Grand Finale 的最小整数手牌上限 kk,其中 k≥nk\ge n。
  • 否则输出 IMPOSSIBLE。

原样例

2
2 6
BG
BQWBWW
4 6
GQBW
WWWWQB
3
IMPOSSIBLE

原样例说明

用“手牌/抽牌堆”的形式表示当前局面。第一个测试用例在 k=3k=3 时,一种最优策略如下;手牌中的书写顺序不影响出牌选择。

  1. BG/BQWBWW,打出 B,得到 BQG/WBWW。
  2. BQG/WBWW,打出 Q,得到 BWG/BWW。
  3. BWG/BWW,打出 B,得到 BWG/W。这里由于手牌已满,丢弃了一张抽到的 W。
  4. BWG/W,打出 B,得到 WWG/∅。由于牌堆只剩一张,此次实际只抽到一张。
  5. WWG/∅,打出 G,成功。