## Algorithm

G. Mass Change Queries
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array a consisting of n integers. You have to process q queries to this array; each query is given as four numbers lrx and y, denoting that for every i such that l ≤ i ≤ r and ai = x you have to set ai equal to y.

Print the array after all queries are processed.

Input

The first line contains one integer n (1 ≤ n ≤ 200000) — the size of array a.

The second line contains n integers a1a2, ..., an (1 ≤ ai ≤ 100) — the elements of array a.

The third line contains one integer q (1 ≤ q ≤ 200000) — the number of queries you have to process.

Then q lines follow. i-th line contains four integers lrx and y denoting i-th query (1 ≤ l ≤ r ≤ n1 ≤ x, y ≤ 100).

Output

Print n integers — elements of array a after all changes are made.

Example
input
Copy
`51 2 3 4 533 5 3 51 5 5 11 5 1 5`
output
Copy
`5 2 5 4 5 `

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1, M = 1e2 + 1;
int n, q, s, e, x, y, tar, a[N], seg[4 * N][M], lazy[4 * N];

void build(int at, int l, int r) {
for(int i = 1; i < M; ++i)
seg[at][i] = i;

if(l == r)
return;

int mid = (l + r) >> 1;
build(at << 1, l, mid);
build(at << 1 | 1, mid + 1, r);
}

void pro(int at, int l, int r) {
if(l != r) {
lazy[at << 1] = lazy[at << 1 | 1] = 1;

for(int i = 1; i < M; ++i)
seg[at << 1][i] = seg[at][seg[at << 1][i]],
seg[at << 1 | 1][i] = seg[at][seg[at << 1 | 1][i]];

lazy[at] = 0;
for(int i = 1; i < M; ++i)
seg[at][i] = i;
}
}

void update(int at, int l, int r) {
if(lazy[at] != 0)
pro(at, l, r);

if(l > e || r < s)
return;

if(l >= s && r <= e) {
lazy[at] = 1;
for(int i = 1; i < M; ++i)
if(seg[at][i] == x)
seg[at][i] = y;
pro(at, l, r);
return;
}

int mid = (l + r) >> 1;
update(at << 1, l, mid);
update(at << 1 | 1, mid + 1, r);
}

int get(int at, int l, int r) {
if(lazy[at] != 0)
pro(at, l, r);

if(l > e || r < s)
return 0;

if(l >= s && r <= e)
return seg[at][tar];

int mid = (l + r) >> 1;
return get(at << 1, l, mid) + get(at << 1 | 1, mid + 1, r);
}

int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", a + i);

build(1, 1, n);

scanf("%d", &q);
for(int i = 0; i < q; ++i) {
scanf("%d %d %d %d", &s, &e, &x, &y);
update(1, 1, n);
}

for(int i = 1; i <= n; ++i) {
s = e = i;
tar = a[i];
printf("%s%d", i == 1 ? "" : " ", get(1, 1, n));
}
puts("");

return 0;
}``````
Copy The Code &

Input

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

Output

cmd
5 2 5 4 5