Problem Description

There are $ N $ people numbered from $ 1 $ to $ N $. Initially, the name of person $i\ (1\ \leq\ i\ \leq\ N)$ is $ S_i $.

For each query $i=1,2,\ldots,Q$, process the following query and then output the final names of each person.

• Sort the $ N $ people in lexicographical order of their names (if the names are the same, sort by their numbers in ascending order), and change the name of the $ X_i $-th person from the front to $ T_i $.

Input Format

The input is given from the 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 Format

Output the names of each person after processing all queries, separated by spaces in ascending order of their numbers.

Sample Input and Output

Sample Input #1

3 3
taro jiro sabro
1 taro
2 jiro
3 taro

Sample Output #1

jiro taro sabro

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

Notes/Hints

Constraints

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

Sample Explanation 1

Initially, the names of the $ N=3 $ people in order of their numbers are taro, jiro, sabro.
- In the query for $ i=1 $, sorting the people by their names lexicographically results in person $ 2 $, person $ 3 $, person $ 1 $. The name of the $ X_1=1 $-th person, which is person $ 2 $, is changed to $ T_1 $, resulting in the names taro, taro, sabro in order of their numbers.
- In the query for $ i=2 $, sorting the people by their names lexicographically results in person $ 3 $, person $ 1 $, person $ 2 $. The name of the $ X_2=2 $-th person, which is person $ 1 $, is changed to $ T_2 $, resulting in the names jiro, taro, sabro in order of their numbers.
- In the query for $ i=3 $, sorting the people by their names lexicographically results in person $ 1 $, person $ 3 $, person $ 2 $. The name of the $ X_3=3 $-th person, which is person $ 2 $, is changed to $ T_3 $, resulting in the names jiro, taro, sabro in order of their numbers. Note that as in the query for $ i=3 $, there may be cases where the name of the $ X_i $-th person does not change before and after the query.

见题面 Input 部分

见题面 Output 部分