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. 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). For each test case, output an integer: the maximum number of people seated. In the first test case, there are