题目描述

小 M 所在的学校有一个礼堂，礼堂里至多能同时进行一个活动，因此需要预约。每个活动占据某一天的上午、下午或者晚上。

礼堂负责人按照时间顺序接收到了 $n$ 个活动预约，其中第 $i$ 个活动预约描述了活动如下信息：

• 活动类型 $type_i$：一个大写字母，O 表示学校官方活动，C 表示社团活动，P 表示个人活动。
• 活动日期 $date_i$：使用 YYYYMMDD 格式表示，例如 20250411 表示 $2025$ 年 $4$ 月 $11$ 日。
• 活动时间 $time_i$：一个大写字母，M 表示上午，A 表示下午，E 表示晚上。

负责人每收到一个新的活动预约，会直接加入日程，接下来重复执行如下流程，直到日程里没有冲突：

• 我们规定学校官方活动优先于社团活动优先于个人活动。如果冲突的两个活动预约类型不同，那么把优先程度更低的活动向后挪一天（活动时间不变）。
• 如果冲突的两个活动类型相同，那么遵循先到先得的原则，把较后预约的活动向后挪一天。
• 注意向后挪动一天可能引发新的冲突，此时对于新冲突的两个活动，仍然按照上述方案调整。

给出这 $n$ 个活动预约的信息，请输出最终每个活动在日程里的活动日期，按照活动预约的提交顺序输出。

输入格式

输入的第一行有一个正整数 $n$，表示活动个数。

之后 $n$ 行，每行依次输入一个大写字母 $type_i$、一个八位数日期 $date_i$ 和一个大写字母 $time_i$，表示一个活动预约，具体含义同题目描述。

输出格式

输出 $n$ 行，每行一个八位数日期，其中第 $i$ 行表示的是第 $i$ 个提交的活动预约最终的日期。

5
P 20250419 A
O 20250419 A
C 20250419 A
C 20250419 E
C 20250420 A

20250422
20250419
20250420
20250419
20250421

6
P 20280228 M
P 20280228 M
P 20290228 A
P 20290228 A
P 20991231 E
P 20991231 E

20280228
20280229
20290228
20290301
20991231
21000101

5
C 20250419 E
C 20250420 A
P 20250419 A
O 20250419 A
C 20250419 A

20250419
20250420
20250422
20250419
20250421

提示

【样例 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$		不保证
$4$		保证	不保证
$5,6$		不保证
$7$	$5000$	保证
$8,9,10$		不保证

• 特殊性质 A：每个活动的最终日期和预约日期在同一个月内（例如样例 1）。
• 特殊性质 B：每个活动预约仅产生至多一次冲突，不会连续冲突（例如样例 2）。