P8890 [Beginner Contest #7] The Happiest Part of Playing ACM Is Watching the Scroll and Reading Team Names (Hard Version)

**This problem has exactly the same statement as [I1](https://www.luogu.com.cn/problem/B3692). The only difference is the ranges of $m$ and $K$.** At the recently concluded ICPC Hangzhou Regional, a certain E experienced an exciting scoreboard scroll. She found that the happiest part of playing ACM is watching the scroll and reading team names.

An official ICPC contest lasts for $5$ hours. A team’s rank is determined by the number of solved problems and the penalty time. Teams that solve more problems rank higher. If the number of solved problems is the same, the team with a smaller penalty time ranks higher. Teams with the same number of solved problems and the same penalty time share the same rank. In this problem, ties may occur; in that case, the team that appears earlier in the submission log is considered to rank higher. Penalty time is determined by the time when problems are solved and the number of unsuccessful submissions before solving. The penalty time equals the sum, over all solved problems, of the number of minutes from the contest start to the accepted submission time, plus $20$ minutes multiplied by the number of unsuccessful submissions before that acceptance. For example, if a team solves problem G at $1:28:35$, and before that there were $3$ unsuccessful submissions on G, then the total contribution of G to the penalty is $88+3 \times 20=148$ minutes. **Note that only unsuccessful submissions for solved problems are counted into the penalty.** For example, if a team has $14$ unsuccessful submissions on problem I, but never solves problem I before the contest ends, then these $14$ unsuccessful submissions are not counted into the penalty. **After a team has solved a problem, any further submissions on that problem (whether accepted or not) do not affect the solve result or the penalty for that problem.** During the contest, contestants may submit code for any problem at any time. The code is judged immediately and a result is returned ($\texttt{Accepted}$, $\texttt{Time Limit Exceeded}$, $\texttt{Memory Limit Exceeded}$, $\texttt{Presentation Error}$, $\texttt{Wrong Answer}$, $\texttt{Runtime Error}$). Among them, $\texttt{Accepted}$ means solved; all other results mean unsolved. During the first four hours ($0:00:00 \sim 4:00:00$), every submission of each team is reflected on the scoreboard. During the last hour ($4:00:01 \sim 5:00:00$), the scoreboard is frozen; all submissions are shown as pending on the scoreboard for the corresponding team and problem (the submitting team knows the judgment result). After the contest ends, the exciting “scrolling the scoreboard” session begins. The guest will follow the frozen scoreboard order, from the last place to the first place: **they first read out the team name**, then, in order from problem A to the last problem, they reveal whether each pending problem on the scoreboard is finally solved. If a pending submission is revealed as solved, the ranks of all teams are recomputed immediately. Clearly, teams whose scrolling has already been completed (their names have been read by the guest, and all pending results have been revealed) will no longer be affected. If the team’s rank rises, the guest immediately starts the scrolling for the next team. Therefore, a team’s name may be read multiple times. For example, a team named “囤题” did not solve any problem in the first four hours and was last when the scoreboard froze. After the freeze, they solved all thirteen problems in a row. Then the guest might read this team’s name seven or eight times. Of course, once the team rises to first place, its rank will no longer change. Even if a later revealed result is solved, if its rank does not change, the guest will not read its name again. Now you are given the complete submission log of an ICPC contest. Please output, in order, the team names read out by the guest during the scrolling session. **Teams with no submission records will not appear on the scoreboard, and their names will not be read during the scrolling session.**

The first line contains three integers $n,m,K$, representing the number of problems in the contest, the number of teams in the contest, and the number of submission records. The next $K$ lines each contain four space-separated strings describing one submission record. The first is in the form $x:yy:zz$, meaning the submission was made at $x$ hours $yy$ minutes $zz$ seconds after the contest started. The second string is an uppercase English letter, representing the problem ID ($\texttt{A,B,} \cdots$). The third string is the team name; it is guaranteed that the team name contains no spaces. The fourth string (may contain spaces, but is one of the six judgment results listed in the “Description”) is the judgment result of this submission. See the “Description” section for the meanings of these strings.

Output several lines, each being a team name read out by the guest, in order.

### Sample Explanation Before the freeze, team $\texttt{abc}$ solved only problem $\texttt{A}$, and had one wrong submission before the first accepted submission at the second second, so the penalty time is $20$ minutes. Team $\texttt{bcd}$ also solved only problem $\texttt{A}$, and had no wrong submissions before the first accepted submission at $0:19:38$, so the penalty time is $19$ minutes. After the freeze, team $\texttt{abc}$ solved problem $\texttt{B}$. When the scrolling session starts, since the submissions after the freeze have not been revealed, we temporarily consider that both $\texttt{abc}$ and $\texttt{bcd}$ have solved only one problem, and the former has a larger penalty time, so it ranks lower. Following the rule from last place to first place, team $\texttt{abc}$ is read first, and the results of its submissions after the freeze are revealed. It solved problem $\texttt{B}$, so its solved count is updated to $2$, and its penalty time is updated as well. Then the ranks of all teams are recomputed immediately. Since now $\texttt{abc}$ has solved more problems than $\texttt{bcd}$, $\texttt{abc}$ becomes first, and $\texttt{bcd}$ becomes last (second). After that, team $\texttt{bcd}$ is read. Since it made no submissions after the freeze, the ranks do not change at this time, and the guest proceeds to scroll the team above it. Finally, team $\texttt{abc}$ is read, and the scrolling session ends. Note that during the scrolling process, submissions are revealed problem by problem. That is, if a team solved multiple problems after the freeze, during its scrolling process, as long as (in order from problem $\texttt{A}$ to the last problem) the first pending problem is revealed as solved, then the later pending problems are not revealed for the moment. Instead, the rank update process happens immediately, and it is possible that the scrolling switches to another team. ### Constraints For $100\%$ of the testdata, $1 \le n \le 20$, $1 \le m \le 2 \times 10^5$, $1 \le K \le 2 \times 10^6$, $0 \leq x \leq 5$, $00 \leq yy < 60$, $00 \leq zz < 60$, and when $x = 5$ it is guaranteed that $yy = zz = 00$. It is guaranteed that the submission records are given in non-decreasing order of submission time, i.e., a submission record given earlier will not be later than a submission record given afterward. Problem IDs are uppercase letters $\texttt{A} \sim \texttt{Z}$. All team names are strings of lowercase letters of length at most $50$. Each judgment result is one of the $6$ kinds given in the statement. Translated by ChatGPT 5