Update Book Genres

You are given n books and m genres. Initially, each book has a genre indicated by an integer. Then, t transactions are performed. Each transaction consists of a book identifier and a new genre identifier, which updates the genre of that book.

Your task is to update the genres of the books according to the transactions and output the final genres of all books in order.

More formally, let \( n \) be the number of books, \( m \) the number of genres, and \( t \) the number of transactions. Initially, you are given a sequence \( B = [b_1, b_2, \dots, b_n] \) where \( b_i \) is the genre of the \( i\text{-th} \) book. For each transaction represented as a pair \( (i, g) \), update \( b_i = g \). Finally, output the updated sequence \( B \).

inputFormat

The input is given via standard input (stdin) and is formatted as follows:

n m
b1 b2 ... bn
t
id1 new_genre1
id2 new_genre2
... 
idt new_genret

Here:

• \( n \): the number of books.
• \( m \): the number of genres.
• \( b_1, b_2, \dots, b_n \): the initial genres of the books.
• \( t \): the number of transactions.
• Each subsequent line contains two integers: book id and new genre id.

outputFormat

Output a single line containing \( n \) integers separated by a space, which represent the updated genres of the books after all transactions have been processed. The output should be printed to standard output (stdout).

6 3
1 2 3 1 2 3
5
1 3
2 1
6 1
3 2
5 3

3 1 2 1 3 1