Independent Copy: Mutating B Does Not Change A

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem

Given $A=(a_0,\ldots,a_{n-1})$, first create an independent copy $B$ with $b_i=a_i$ for every valid index. Then process $q$ updates $(p,x)$ on $B$ only, each performing $b_p\leftarrow x$. All indices are valid and the same position may be updated more than once. Array $A$ must remain unchanged.

Input

The first line contains $n,q$. The second line contains $A$. Each of the next $q$ lines contains $p,x$ with $0\le p<n$.

Output

Print the unchanged $A$ on the first line and final $B$ on the second line.

Subtask

Subtask 1 (20 points): $1\le n\le10$, $0\le q\le10$.

Subtask 2 (30 points): $1\le n\le100$, $0\le q\le100$.

Subtask 3 (50 points): $1\le n\le1000$, $0\le q\le1000$.

Example

Input

4 3
5 6 7 8
1 10
3 -2
1 99

Output

5 6 7 8
5 99 7 -2

Explanation

Only the independent copy is updated; the source array remains unchanged.