[语言月赛 202504] 礼堂预约

小 M 所在的学校有一个礼堂，礼堂里至多能同时进行一个活动，因此需要预约。每个活动占据**某一天**的上午、下午或者晚上。 礼堂负责人**按照时间顺序**接收到了 $n$ 个活动预约，其中第 $i$ 个活动预约描述了活动如下信息： - 活动类型 $type_i$：一个大写字母，`O` 表示学校官方活动，`C` 表示社团活动，`P` 表示个人活动。 - 活动日期 $date_i$：使用 `YYYYMMDD` 格式表示，例如 `20250411` 表示 $2025$ 年 $4$ 月 $11$ 日。 - 活动时间 $time_i$：一个大写字母，`M` 表示上午，`A` 表示下午，`E` 表示晚上。 负责人每收到一个新的活动预约，会直接加入日程，接下来重复执行如下流程，直到日程里没有冲突： - 我们规定学校官方活动**优先于**社团活动**优先于**个人活动。如果冲突的两个活动预约类型不同，那么把优先程度更低的活动向后挪一天（活动时间不变）。 - 如果冲突的两个活动类型相同，那么遵循先到先得的原则，把较后预约的活动向后挪一天。 - 注意向后挪动一天可能引发新的冲突，此时对于新冲突的两个活动，仍然按照上述方案调整。 给出这 $n$ 个活动预约的信息，请输出最终每个活动在日程里的活动日期，**按照活动预约的提交顺序输出。** ## Input 输入的第一行有一个正整数 $n$，表示活动个数。 之后 $n$ 行，每行依次输入一个大写字母 $type_i$、一个八位数日期 $date_i$ 和一个大写字母 $time_i$，表示一个活动预约，具体含义同题目描述。 ## Output 输出 $n$ 行，每行一个八位数日期，其中第 $i$ 行表示的是第 $i$ 个提交的活动预约最终的日期。 [samples] ## Note 【样例 1 解释】 活动 $1$ 是个人活动，希望在 $2025$ 年 $4$ 月 $19$ 日下午进行，没有冲突。 活动 $2$ 是官方活动，希望在 $2025$ 年 $4$ 月 $19$ 日下午进行，和活动 $1$ 冲突。因此，活动 $1$ 被修改到 $4$ 月 $20$ 日下午。 活动 $3$ 是社团活动，希望在 $2025$ 年 $4$ 月 $19$ 日下午进行，和活动 $2$ 冲突。 - 由于活动 $2$ 是官方活动，所以把活动 $3$ 延后一天到 $4$ 月 $20$ 日下午。 - 然而现在活动 $3$ 和活动 $1$ 冲突，而活动 $1$ 优先程度更低，所以活动 $1$ 被修改到 $4$ 月 $21$ 日下午。 活动 $4$ 是社团活动，希望在 $2025$ 年 $4$ 月 $19$ 日晚上进行，没有冲突。 活动 $5$ 是社团活动，希望在 $2025$ 年 $4$ 月 $20$ 日下午进行，和活动 $3$ 冲突。 - 由于活动 $3,5$ 都是社团活动，按照先到先得原则，把活动 $5$ 延后到 $2025$ 年 $4$ 月 $21$ 日下午。 - 现在活动 $5$ 和活动 $1$ 冲突，所以把活动 $1$ 延后到 $2025$ 年 $4$ 月 $22$ 日。 【样例 2 解释】 注意日期的计算。 【样例 3 解释】 按照收到活动预约的时间给出，不代表活动预约按照 $date_i$ 排序。 【数据范围】 对于全部数据，保证 $1\le n\le 5000$，$type_i$ 一定是 `O`、`C`、`P` 之一，$time_i$ 一定是 `M`，`A`，`E` 之一，$date_i$ 一定是 $2000$ 年 $1$ 月 $1$ 日到 $2099$ 年 $12$ 月 $31$ 日之间、真实存在的日期。（注意并不保证最终的日期在这个范围内。） 本题共有 $10$ 个测试点，每个 $10$ 分。部分测试点有特殊性质，具体如下： |测试点编号|$n\le$|特殊性质 A|特殊性质 B| |:-:|:-:|:-:|:-:| |$1,2$|$500$|保证|保证| |$3$|$500$|不保证|保证| |$4$|$500$|保证|不保证| |$5,6$|$500$|不保证|不保证| |$7$|$5000$|保证|保证| |$8,9,10$|$5000$|不保证|不保证| - 特殊性质 A：每个活动的最终日期和预约日期在同一个月内（例如样例 1）。 - 特殊性质 B：每个活动预约仅产生至多一次冲突，不会连续冲突（例如样例 2）。