题目描述

这是本题的困难版本，区别在于 $n,x,s$ 的限制更大。只有解决了所有版本后才能 hack。

题意与简单版相同：有 $x$ 张桌子，每张桌子 $s$ 个座位；内向者 I 只能坐空桌，外向者 E 只能坐非空桌，双向者 A 可以坐任意桌。队伍顺序固定，每个人到来时必须立即安排或请离。

请你求出最多能让多少人入座。

输入格式

第一行包含一个整数 $t$，表示测试组数。

每组测试数据第一行包含三个整数 $n,x,s$。

第二行包含一个长度为 $n$ 的字符串 $u$，仅由 A、E、I 组成。

输出格式

对于每组测试数据，输出一个整数，表示最多能入座的人数。

数据范围

• $1 \le t \le 10^4$
• $1 \le n,x,s \le 2\cdot 10^5$
• 所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$

6
5 2 2
EIAIE
20 5 5
AEIEEEEIEAAEIEEEEIEA
8 2 4
AAAAAIEE
8 4 2
AIEAEAAI
8 3 3
AIEAEAAI
4 2 2
IAEE

4
20
7
7
7
4

提示

在第一个测试案例中，有 $2$ 张桌子，每张桌子有 $2$ 个座位。下面是实现最多座位数的方法之一。

第一个人性格外向。由于所有桌子都是空的，他们必须离开聚会。

第二个人性格内向。爱丽丝可以把他们分配到第一张空桌。

第三个人性格内向。爱丽丝可以将他们分配到第一张桌子。

第四个人性格内向。爱丽丝可以把他们分配到第二张空桌。

第五个人性格外向。爱丽丝可以把他们分配到第二张桌子，这张桌不是空的。

这样，聚会上就有四个座位。这是最大值，因为聚会上只有四个座位。

来源

Codeforces Round 2232 C2 - Seating Arrangement (Hard Version)