分数: 6 点
问题陈述
有 N 人,其 ID 来自 1 to N。最初,人 i (1 \leq i \leq N) 被命名为 S_i.
为每个人处理以下查询后打印每个人的姓名 i=1, 2, \ldots, Q 按顺序。
- 让人们按照名字的字典序升序站成一排(如果名字相同,则按ID升序排列),并重命名 X_i从前面到第 T_i.
约束
- 1 \leq N,Q \leq 10^5
- S_i 是长度介于 1 和 5 (含)由小写英文字母组成。
- 1 \leq X_i \leq N
- T_i 是长度介于 1 和 5 (含)由小写英文字母组成。
- N, Q,和 X_i 是整数。
输入
输入由标准输入按以下格式给出:
N Q S_1 S_2 \ldots S_N X_1 T_1 X_2 T_2 \vdots X_Q T_Q
输出
打印姓名 N 人按照ID升序排列,用空格分隔,按顺序处理完所有查询后。
示例输入 1
3 3 taro jiro sabro 1 taro 2 jiro 3 taro
示例输出 1
jiro taro sabro
最初, N=3 人被命名 taro, jiro, sabro 按 ID 升序排列。
- 在查询中 i=1,当它们按照名字的字典升序排成一排时,它们的顺序是 2, 3, 1。的 X_1=1- 前面的第一个人,人 2,重命名为 T_1。现在,人们被命名为
taro,taro,sabro按 ID 升序排列。 - 在查询中 i=2,当它们按照名字的字典升序排成一排时,它们的顺序是 3, 1, 2。的 X_2=2- 前面的第一个人,人 1,重命名为 T_2。现在,人们被命名为
jiro,taro,sabro按 ID 升序排列。 - 在查询中 i=3,当它们按照名字的字典升序排成一排时,它们的顺序是 1, 3, 2。的 X_3=3- 前面的第一个人,人 2,重命名为 T_3。现在,人们被命名为
jiro,taro,sabro按 ID 升序排列。
请注意,如查询中所示 i=3,名称 X_i- 第一个人在查询中可能保持不变。
示例输入 2
10 10 yo gaaj uab y reah y dyg ix rwq p 10 tvbvr 8 ax 7 xr 9 vw 10 ky 10 wlxtw 2 guoux 10 wbct 9 zbuxx 5 gq
示例输出 2
tvbvr gaaj ax zbuxx reah gq guoux ix wbct p