AT_past202112_m 名前の変更

[problemUrl]: https://atcoder.jp/contests/past202112-open/tasks/past202112_m $ 1 $ から $ N $ までの番号が振られた、$ N $ 人の人がいます。はじめ、人 $ i\ (1\ \leq\ i\ \leq\ N) $ の名前は $ S_i $ です。 $ i=1,2,\ldots,Q $ について順に以下のクエリを処理したあと、最終的な各人の名前を出力してください。 - $ N $ 人を名前の辞書順で小さい順（名前が同じ場合は番号の若い順）に整列させ、前から $ X_i $ 人目の人の名前を $ T_i $ に変える。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ S_1 $ $ S_2 $ $ \ldots $ $ S_N $ $ X_1 $ $ T_1 $ $ X_2 $ $ T_2 $ $ \vdots $ $ X_Q $ $ T_Q $

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

### 制約 - $ 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 $ は整数 ### Sample Explanation 1 はじめ、$ 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 $ 人目の名前に変化がない場合も存在することに注意してください。