Mass Change Queries

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Given an array of $n$ integers in the range 1 to 100, process $q$ queries l r x y: for every $i\in[l,r]$ with $a_i=x$, replace it by $y$.

After all queries, print the final array.

Input

The first line contains $n$. The second line contains the array. The third line contains $q$. Each of the next $q$ lines contains l r x y.

Output

Print the $n$ elements after all queries have been processed.

Subtasks

• Subtask 1 (20%): n,q≤30; all other conditions are unchanged.

• Subtask 2 (30%): n,q≤3000; all other conditions are unchanged.

• Subtask 3 (50%): full constraints:

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

• $1\le a_i\le100$

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

• $1\le x,y\le100$

Examples

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

Explanation

The three replacements transform the sample array successively to [1,2,5,4,5], then [1,2,1,4,1], and finally [5,2,5,4,5].