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 l, r, x 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 a1, a2, ..., 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 l, r, x and y denoting i-th query (1 ≤ l ≤ r ≤ n, 1 ≤ x, y ≤ 100).

Output

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

Example

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 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	final static int mod = 1_000_000_007;
	
	static DSU[] set;
	static int[] a;
	static int n, size, count;
	
	public static void main(String[] args) throws Exception {

		STDIN scan = new STDIN();
		PrintWriter pw = new PrintWriter(System.out);

		n = scan.nextInt(); size = (int) Math.sqrt(n); count = (n + size - 1) / size;
		set = new DSU[count]; a = new int[n];
		for(int i = 0; i < count; i++) set[i] = new DSU(101);
		for(int i = 0; i < n; i++) a[i] = scan.nextInt();
		int q = scan.nextInt();
		while(q-- > 0)
			add(scan.nextInt()-1, scan.nextInt()-1, scan.nextInt(), scan.nextInt());
		restoreAll();
		for(int i = 0; i < n; i++) pw.print(a[i] + " ");
		pw.flush();
	}
	
	static void add(int l, int r, int x, int y) {
		if(x == y) return;
		for(int i = 0; i * size < n; i++)
			if(l <= i * size && (i + 1) * size - 1 <= r)
				set[i].change(x, y);
		int left = l / size;
		if(size * left != l) {
			restore(left);
			for(int i = l; i < Math.min(r + 1, size * (left + 1)); i++)
				if(a[i] == x) a[i] = y;
		}
		int right = r / size;
		if(size * (right + 1) - 1 != right) {
			restore(right);
			for(int i = Math.max(l, size * right); i <= r; i++)
				if(a[i] == x) a[i] = y;
		}
	}
	
	static void restore(int x) {
		for(int i = x * size; i < n && i < (x + 1) * size; i++)
			a[i] = set[x].getVal(a[i]);
		set[x].clear();
	}
	
	static void restoreAll() {
		for(int i = 0; i < count; i++)
			restore(i);
	}
	
	static class DSU{
		int[] par, val, index;
		
		DSU(int len) {
			par = new int[len]; val = new int[len]; index = new int[len]; clear();
		}		
		void clear() {
			for(int i = 0; i < par.length; i++)	par[i] = val[i] = index[i] = i;
		}		
		int find(int x) {
			return (x == par[x]) ? x : (par[x] = find(par[x])); 
		}
		void change(int x, int y) {
			int a = find(index[x]), b = find(index[y]);
			if(val[a] != x) return;
			if(val[b] == y) par[a] = b;
			else index[val[a] = y] = a;
		}
		int getVal(int x) {
			return val[find(x)];
		}
	}
	
	static class STDIN {
		BufferedReader br;
		StringTokenizer st;

		public STDIN() {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = null;
		}

		boolean hasNext() throws Exception {
			if (!st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.hasMoreTokens();
		}

		int nextInt() throws Exception {
			return Integer.parseInt(next());
		}

		long nextLong() throws Exception {
			return Long.parseLong(next());
		}

		double nextDouble() throws Exception {
			return Double.parseDouble(next());
		}

		String next() throws Exception {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		String nextLine() throws Exception {
			return br.readLine();
		}
	}
}