M - Deadnames Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

1 から N までの番号が振られた、N 人の人がいます。はじめ、人 i\ (1 \leq i \leq N) の名前は S_i です。

i=1,2,\ldots,Q について順に以下のクエリを処理したあと、最終的な各人の名前を出力してください。

  • N 人を名前の辞書順で小さい順（名前が同じ場合は番号の若い順）に整列させ、前から 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

出力

クエリをすべて順に処理したあとの各人の名前を、空白区切りで番号の昇順に出力せよ。

入力例 1

3 3
taro jiro sabro
1 taro
2 jiro
3 taro

出力例 1

jiro taro sabro

はじめ、N=3 人の名前は番号順に taro, jiro, sabro です。

  • i=1 のクエリにおいて、各人を名前の辞書順で小さい順に整列させると人 2、人 3、人 1 となります。前から X_1=1 人目である人 2 の名前が T_1 に変更され、3 人の名前は番号順に taro, taro, sabro となります。
  • i=2 のクエリにおいて、各人を名前の辞書順で小さい順に整列させると人 3、人 1、人 2 となります。前から X_2=2 人目である人 1 の名前が T_2 に変更され、3 人の名前は番号順に jiro, taro, sabro となります。
  • i=3 のクエリにおいて、各人を名前の辞書順で小さい順に整列させると人 1、人 3、人 2 となります。前から X_3=3 人目である人 2 の名前が T_3 に変更され、3 人の名前は番号順に jiro, taro, sabro となります。

この入出力例における 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

Score : 6 points

Problem Statement

There are N people, with IDs from 1 to N. Initially, Person i (1 \leq i \leq N) is named S_i.

Print the name of each person after processing the following query for each i=1, 2, \ldots, Q in order.

  • Make the people stand in a row in lexicographically ascending order of name (in case of the same name, ascending order of ID), and rename the X_i-th person from the front to T_i.

Constraints

  • 1 \leq N,Q \leq 10^5
  • S_i is a string of length between 1 and 5 (inclusive) consisting of lowercase English letters.
  • 1 \leq X_i \leq N
  • T_i is a string of length between 1 and 5 (inclusive) consisting of lowercase English letters.
  • N, Q, and X_i are integers.

Input

Input is given from Standard Input in the following format:

N Q
S_1 S_2 \ldots S_N
X_1 T_1
X_2 T_2
\vdots
X_Q T_Q

Output

Print the names of the N people in ascending order of ID, separated by spaces, after processing all queries in order.

Sample Input 1

3 3
taro jiro sabro
1 taro
2 jiro
3 taro

Sample Output 1

jiro taro sabro

Initially, the N=3 people are named taro, jiro, sabro in ascending order of ID.

  • In the query with i=1, when they stand in a row in lexicographically ascending order of name, they are in the order 2, 3, 1. The X_1=1-st person from the front, Person 2, is renamed to T_1. Now, the people are named taro, taro, sabro in ascending order of ID.
  • In the query with i=2, when they stand in a row in lexicographically ascending order of name, they are in the order 3, 1, 2. The X_2=2-nd person from the front, Person 1, is renamed to T_2. Now, the people are named jiro, taro, sabro in ascending order of ID.
  • In the query with i=3, when they stand in a row in lexicographically ascending order of name, they are in the order 1, 3, 2. The X_3=3-rd person from the front, Person 2, is renamed to T_3. Now, the people are named jiro, taro, sabro in ascending order of ID.

Note that, as seen in the query with i=3, the name of the X_i-th person may remain unchanged in a query.

Sample Input 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

Sample Output 2

tvbvr gaaj ax zbuxx reah gq guoux ix wbct p