Bản sao độc lập: sửa B không làm đổi A

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng ban đầu

Trước tiên tạo một bản sao độc lập $B$ bằng

Sau đó thực hiện lần lượt $q$ phép cập nhật chỉ trên $B$. Mỗi phép cập nhật gồm cặp $(p,x)$ và thực hiện

Mọi chỉ số $p$ đều hợp lệ. Các phép cập nhật có thể tác động nhiều lần lên cùng một vị trí.

Mảng $A$ phải giữ nguyên hoàn toàn sau khi $B$ đã được tạo.

Input

Dòng đầu chứa $n,q$. Dòng thứ hai chứa $n$ số nguyên của $A$. Mỗi trong $q$ dòng tiếp theo chứa hai số nguyên $p,x$ với $0\le p<n$.

Output

Dòng thứ nhất in mảng $A$ ban đầu. Dòng thứ hai in mảng $B$ sau tất cả cập nhật.

Subtask

Subtask 1 (20 điểm): $1\le n\le10$, $0\le q\le10$.

Subtask 2 (30 điểm): $1\le n\le100$, $0\le q\le100$.

Subtask 3 (50 điểm): $1\le n\le1000$, $0\le q\le1000$.

Ví dụ

Input

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

Output

5 6 7 8
5 99 7 -2

Giải thích

Sau khi copy, sửa $B_1$, $B_3$, rồi lại $B_1$. Mảng $A$ vẫn là 5 6 7 8.