← 返回题目列表

AtCoder · past202112_m

M. 死者姓名

中文机器翻译题面 查看原题

分数: 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