CF2232C2.Seating Arrangement (Hard Version)

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.

Alice's friends have come to the party, and now they are lining up to enter the party.

There are $x$ tables at the party with $s$ seats each. Each seat can only hold one person.

Each friend has one of these three following personalities:

• 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.

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.

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.

Note that once a friend is seated, they are not allowed to move even if they are not seated according to their personality anymore.

这是本题的困难版本。两个版本的区别在于：在本版本中，$n$、$x$、$s$、$t$ 的约束更大。仅当您已解决本题的所有版本后，才可进行 Hack。

Alice 的朋友们来到派对现场，现在他们正排成一队依次入场。

派对现场共有 $x$ 张桌子，每张桌子有 $s$ 个座位。每个座位至多容纳一人。

每位朋友具有以下三种性格之一：

• 内向者（I）：必须坐在一张空桌子上；
• 外向者（E）：必须坐在一张非空桌子上；
• 中性者（A）：可以坐在任意桌子上。

初始时，所有座位均为空。但由于 Alice 正在吃蛋糕，她的朋友们已自行排好队伍，而 Alice 无法更改该顺序。对于队伍中的每个人，Alice 必须为其分配一张桌子，或将其拒之门外。每个人在下一个人被分配前即完成就座。

为了让派对充满欢乐，Alice 希望尽可能多地让朋友们入座。请帮她求出最多能安排多少位朋友入座。

注意：一旦某位朋友被安排就座，其座位便不可再移动，即使后续该座位状态不再满足其性格要求（例如，内向者所坐的桌子后来又坐了其他人，这仍是允许的）。

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.

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.

It is guaranteed that the sum of $n$ for all test cases is at most $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$x$ 和 $s$（$1 \le n,x,s \le 2\cdot 10^5$）——分别表示爱丽丝的朋友数量、桌子数量以及每张桌子的座位数。第二行包含一个长度为 $n$ 的字符串 $u$，仅由字母 A、E 和 I 组成，分别代表双性人格者（ambivert）、外向者（extrovert）和内向者（introvert）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output an integer: the maximum number of people seated.

对于每个测试用例，输出一个整数：最多可以坐多少人。

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.

The first person is an extrovert. Since all tables are empty, they have to leave the party.

The second person is an introvert. Alice can assign them to the first table, which is empty.

The third person is an ambivert. Alice can assign them to the first table.

The fourth person is an introvert. Alice can assign them to the second table, which is empty.

The fifth person is an extrovert. Alice can assign them to the second table, which is not empty.

Thus, four people are seated at the party. This is maximal since there are only four seats at the party.

在第一个测试用例中，共有 $2$ 张桌子，每张桌子有 $2$ 个座位。以下是实现最多就座人数的一种方式。

第一个人是外向者。由于所有桌子均为空，此人必须离开聚会。

第二个人是内向者。爱丽丝可将其安排至第一张空桌子。

第三个人是中间型人格者。爱丽丝可将其安排至第一张桌子。

第四个人是内向者。爱丽丝可将其安排至第二张空桌子。

第五个人是外向者。爱丽丝可将其安排至第二张非空桌子。

因此，共有四人就座于聚会中。该人数已达到最大值，因为聚会上仅有四个座位。