407826: GYM102897 M XCPCIO Board CLI Hard

本题和 easy version 的区别仅仅在于队伍总数 $$$n$$$ 的范围不同，其它均一致。

众所周知，在 *CPC 比赛中，榜单是一个很重要的部分。

最近，在 ICPC 和 CCPC 比赛的举办期间，有一个公益组织在 GitHub 上创建了一个项目，用于渲染 *CPC 的榜单，致力于提供更丰富的关于榜单的数据统计分析。

除了数据统计分析，XCPCIO Board 还提供了如下特性：

• 通过拖动进度条来复现某一时刻的榜单状态。
• 点开每支队伍能够显示该队伍的排名关于时间的变化情况。
• ...

关于 XCPCIO Board 的更多详细信息，欢迎访问 https://board.xcpcio.com。

现在，XCPCIO 希望开发一个 Board 的 CLI 工具，希望您能帮助他们。

首先，XCPCIO 会以一定的格式将队伍数据和提交数据提供给你(具体的数据格式请参考 Input)。

其次，你需要回答用户的 $$$q$$$ 个询问，询问类型如下：

• teamstatus timestamp teamid, 表示询问队伍编号为 teamid 的队伍在时间戳为 timestamp 的时刻的队伍状态, 包括排名、罚时、每道题的 AC 状态、Dirt 率(具体可参考 Output)。
• minrank timestamp teamid, 表示询问队伍编号为 teamid 的队伍在时间戳小于等于 timestamp 之前的时间的比赛过程中排名数值最小是多少。
• maxrank timestamp teamid, 表示询问队伍编号为 teamid 的队伍在时间戳小于等于 timestamp 之前的时间的比赛过程中排名数值最大是多少。
• account timestamp problemid, 表示询问题目编号为 problemid 的题目在时间戳小于等于 timestamp 之前的比赛过程中总的 AC 数量。
• submitcount timestamp problemid, 表示询问题目编号为 problemid 的题目在时间戳小于等于 timestamp 之前的比赛过程中总的提交数量。
• teamcount timestamp problemnum, 表示询问在时间戳小于等于 timestamp 之前的比赛过程中 AC 了 problemnum 道题目的队伍数量。

Dirt 率：所有 AC 了的题目中的 $$$\lfloor \frac{\mbox{非 AC 提交数}}{\mbox{总提交数}} \rfloor$$$。如果还没有 AC 题目，那么你需要输出 "N/A"。

关于罚时的计算：

• 只有 AC 的题目才会计入罚时。
• 一道题目 AC 后，它的计算公式为 $$$\mbox{AC 时间} + \mbox{非 AC 的提交数量} \cdot 20$$$。

关于排名：

• 首先按 AC 题目数量从大到小排名。
• AC 数量相同的情况下，其次按罚时从小到大排名。
• AC 数量和罚时均相同的情况下，最后按队伍编号从小到大排名。

容易证明，按照以上排名规则，不会出现两支队伍排名一致的情况。

并且我们约定在比赛的第 $$$0$$$ 时刻，没有任何提交，每支队伍的排名就是它的队伍编号。

在某一时刻，如果有多发提交，那么在这一时刻整个排行榜如果按一发一发的提交来变化可能会变化很多次。

但是我们在此处约定，如果某一时刻有多发提交，那么这一时刻的排名是基于这些提交产生的结果都应用之后。

也就是说，在一场比赛中，榜单的结果只有 $$$T$$$ 种，当时间戳为 timestamp 时的榜单为所有时间戳小于等于 timestamp 的提交产生的结果榜单。

单组数据评测。

第一行包含 $$$4$$$ 个正整数 $$$n(1 \leq n \leq 10^5),\;T(1 \leq T \leq 10^5),\;m(1 \leq m \leq 10^6),\;p(1 \leq p \leq 13)$$$，表示该场比赛总的队伍数, 总的时间, 总的提交数和题目数量。

接下来 $$$m$$$ 行，每行表示一个提交。包含 $$$3$$$ 个正整数 $$$team_i(1 \leq team_i \leq n),\;problemid_i(1 \leq problemid_i \leq p)$$$, $$$timestamp_i(1 \leq timestamp_i \leq T)$$$, 表示队伍编号, 题目编号和时间戳，以及一个字符串 AC|WA, 表示提交的状态(AC 表示正确通过，WA 表示解答错误)。

第 $$$m + 1$$$ 行包含一个正整数 $$$q(1 \leq q \leq 10^5)$$$，表示询问总数。

接下来 $$$q$$$ 行，每行表示一个询问。

• teamstatus timestamp teamid, 表示询问队伍编号为 teamid 的队伍在时间戳为 timestamp 的时刻的队伍状态, 包括排名、罚时、每道题的 AC 状态、Dirt 率(具体格式可参考 Output)。
• minrank timestamp teamid, 表示询问队伍编号为 teamid 的队伍在时间戳小于等于 timestamp 之前的时间的比赛过程中排名数值最小是多少。
• maxrank timestamp teamid, 表示询问队伍编号为 teamid 的队伍在时间戳小于等于 timestamp 之前的时间的比赛过程中排名数值最大是多少。
• account timestamp problemid, 表示询问题目编号为 problemid 的题目在时间戳小于等于 timestamp 之前的比赛过程中总的 AC 数量。
• submitcount timestamp problemid, 表示询问题目编号为 problemid 的题目在时间戳小于等于 timestamp 之前的比赛过程中总的提交数量。
• teamcount timestamp problemnum, 表示询问在时间戳小于等于 timestamp 之前的比赛过程中 AC 了 problemnum 道题目的队伍数量。

对于以上所有询问类型，都有 $$$1 \leq timestamp \leq T$$$, $$$1 \leq teamid \leq n$$$, $$$1 \leq problemid \leq p$$$, $$$1 \leq problemnum \leq p$$$。

一支队伍如果在 AC 一道题目后继续对该题进行提交，我们认为 AC 之后的提交对数据统计分析没有意义，所以我们提前剔除了这些「脏提交」，或者你可以认为我们提供的数据中不存在这样的提交。

并且数据保证，每支队伍在每一时刻，对于某一道题最多只有一发提交。

需要注意的是，给出的 $$$m$$$ 条提交并不一定是按 timestamp 排序的。

对于每一个询问，输出包含一行。

• teamstatus, 首先是一个正整数表示队伍的排名，接着一个长度为 $$$p$$$ 的字符串表示题目的 AC 情况, 用 $$$\mathbf{[}$$$ 和 $$$\mathbf{]}$$$ 包裹，并且我们约定用 $$$\mathbf{o}$$$ 表示 AC，用 $$$\mathbf{x}$$$ 表示提交过并且 WA 了，用 $$$\mathbf{-}$$$ 表示还未提交, 接着有一个正整数和一个百分号表示 Dirt 率，注意这三部分内容需要用空格间隔，具体可参考样例。
• minrank, 输出包含一行一个整数表示该队伍的最小排名数值。
• maxrank, 输出包含一行一个整数表示该队伍的最大排名数值。
• account, 输出包含一行一个整数表示该题目的 AC 数量。
• submitcount, 输出包含一行一个整数表示该题目的提交数量。
• teamcount, 输出包含一行一个整数表示 AC 了 problemnum 道题目的队伍数量。

5 10 10 13
1 1 5 WA
1 1 6 AC
2 1 1 AC
3 5 5 WA
3 5 6 AC
3 7 1 AC
3 13 10 AC
5 1 1 AC
5 2 1 WA
5 2 2 AC
21
teamstatus 1 1
teamstatus 2 2
teamstatus 3 3
teamstatus 4 4
teamstatus 5 5
minrank 1 1
maxrank 1 5
maxrank 2 5
account 1 1
account 2 1
submitcount 1 1
submitcount 2 1
submitcount 9 13
submitcount 10 13
teamcount 1 1
teamcount 2 1
teamcount 3 2
teamcount 10 1
teamstatus 10 3
teamstatus 1 2
teamstatus 5 1

4 [-------------] N/A
2 [o------------] 0%
3 [------o------] 0%
5 [-------------] N/A
1 [oo-----------] 33%
1
5
5
2
2
2
2
0
1
3
2
1
2
1 [----o-o-----o] 25%
1 [o------------] 0%
4 [x------------] N/A