Truy vấn đổi hàng loạt (Mass Change Queries)

Nguồn: Codeforces

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

Đề bài

Cho mảng $a$ gồm $n$ số nguyên trong miền từ 1 đến 100. Có $q$ truy vấn l r x y: với mọi $i\in[l,r]$ mà $a_i=x$, thay $a_i$ bằng $y$.

Sau khi thực hiện toàn bộ truy vấn, in mảng cuối cùng.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ phần tử. Dòng thứ ba chứa $q$. Mỗi trong $q$ dòng sau chứa l r x y.

Output

In $n$ số là mảng sau toàn bộ truy vấn.

Subtask

• Subtask 1 (20%): n,q≤30; các điều kiện khác giữ như bài đầy đủ.

• Subtask 2 (30%): n,q≤3000; các điều kiện khác giữ như bài đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le n,q\le2\cdot10^5$

• $1\le a_i\le100$

• $1\le l\le r\le n$

• $1\le x,y\le100$

Ví dụ

Input

5
1 2 3 4 5
3
3 5 3 5
1 5 5 1
1 5 1 5

Output

5 2 5 4 5

Giải thích

Mẫu: [1,2,3,4,5]. Đổi 3→5 trên 3..5 được [1,2,5,4,5]; đổi 5→1 trên toàn mảng được [1,2,1,4,1]; cuối cùng 1→5 được [5,2,5,4,5].