座位安排（困难版）AI (CI翻译)
This is the Hard version of the problem. The difference between the versions is that in this version, the constraints on $n$, $x$, $s$, $t$ are larger. You can hack only if you solved all versions of this problem.
这是本题的困难版本。两个版本之间的区别在于，本版本中 $n$、$x$、$s$、$t$ 的约束更大。只有解决了本题的所有版本后，才能进行 hack。AI (CI翻译)
Alice's friends have come to the party, and now they are lining up to enter the party.
Alice 的朋友们来参加聚会了，现在他们正排队进入聚会场地。AI (CI翻译)
There are $x$ tables at the party with $s$ seats each. Each seat can only hold one person.
聚会场地有 $x$ 张桌子，每张桌子有 $s$ 个座位。每个座位只能坐一个人。AI (CI翻译)
Each friend has one of these three following personalities:
每位朋友都有以下三种性格之一：AI (CI翻译)
- Introverts (
I) who have to sit at an empty table - Extroverts (
E) who have to sit at a non-empty table - Ambiverts (
A) who can sit at any table.
- 内向者（
I）必须坐在空桌旁 - 外向者（
E）必须坐在非空桌旁 - 双向性格者（
A）可以坐在任意桌旁
Initially, every seat is empty. However, because Alice was eating cakes, her friends had already formed a line, which Alice cannot change their order. For each person in the line, Alice has to assign them a table or kick them out of the party. Each person is seated before the next person is assigned a table.
最开始时，所有座位都是空的。然而，由于 Alice 当时正在吃蛋糕，她的朋友们已经排好了队，Alice 无法改变他们的顺序。对于队伍中的每个人，Alice 都必须为其安排一张桌子，或者将其赶出聚会。每个人入座后，Alice 才能为下一个人安排座位。AI (CI翻译)
Wanting to have a lot of fun at the party, Alice needs to seat as many people as she can at the party. Help her find the maximum number of friends she can have at the party.
为了让聚会尽可能热闹，Alice 希望尽可能多地让朋友参加聚会。请帮助她求出最多能让多少位朋友参加聚会。AI (CI翻译)
Note that once a friend is seated, they are not allowed to move even if they are not seated according to their personality anymore.
注意，一旦朋友入座，即使之后他们的座位不再符合其性格要求，也不允许他们移动。AI (CI翻译)
Input
输入格式
AI (CI翻译)Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。AI (CI翻译)
The first line of each test case contains three integers $n$, $x$, and $s$ ($1 \le n,x,s \le 2\cdot 10^5$) – the number of Alice's friends, the number of tables, and the number of seats per table. The second line contains a string $u$ of length $n$ consisting only of the letters A, E, and I, representing an ambivert, extrovert, and introvert respectively.
每个测试用例的第一行包含三个整数 $n$、$x$ 和 $s$（$1 \le n,x,s \le 2\cdot 10^5$），分别表示 Alice 的朋友数量、桌子数量以及每张桌子的座位数。第二行包含一个长度为 $n$ 的字符串 $u$，只由字母 A、E 和 I 构成，分别表示双向性格者、外向者和内向者。AI (CI翻译)
It is guaranteed that the sum of $n$ for all test cases is at most $2 \cdot 10^5$.
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each test case, output an integer: the maximum number of people seated.
对于每个测试用例，输出一个整数，即最多能入座的人数。AI (CI翻译)
Note
说明
AI (CI翻译)In the first test case, there are $2$ tables with $2$ seats each. Here is one of the ways to achieve the maximum number of people seated.
在第一个测试用例中，有 $2$ 张桌子，每张桌子有 $2$ 个座位。以下是一种使入座人数达到最大值的方法。AI (CI翻译)
The first person is an extrovert. Since all tables are empty, they have to leave the party.
第一个人是外向者。由于所有桌子都是空的，他只能离开聚会。AI (CI翻译)
The second person is an introvert. Alice can assign them to the first table, which is empty.
第二个人是内向者。Alice 可以将他安排到第一张空桌旁。AI (CI翻译)
The third person is an ambivert. Alice can assign them to the first table.
第三个人是双向性格者。Alice 可以将他安排到第一张桌旁。AI (CI翻译)
The fourth person is an introvert. Alice can assign them to the second table, which is empty.
第四个人是内向者。Alice 可以将他安排到第二张空桌旁。AI (CI翻译)
The fifth person is an extrovert. Alice can assign them to the second table, which is not empty.
第五个人是外向者。Alice 可以将他安排到第二张非空桌旁。AI (CI翻译)
Thus, four people are seated at the party. This is maximal since there are only four seats at the party.
因此，共有四个人参加了聚会。由于聚会场地总共只有四个座位，这是最多的入座人数。AI (CI翻译)
样例
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
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。