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.StringTokenizer;

public class Main {

	final static int mod = 1_000_000_007;
	

	public static void main(String[] args) throws Exception {

		STDIN scan = new STDIN();
		pw = new PrintWriter(System.out);
		
		int n = scan.nextInt();
		a = new int[n];
		for(int i = 0; i < n; i++) a[i] = scan.nextInt();		
		int height = (int) Math.ceil(Math.log(n) / Math.log(2));
		tree = new int[2 * (1 << height) - 1][101];
		changed = new boolean[tree.length];
		build(0, 0, n-1);
		int q = scan.nextInt();
		while(q-- > 0)
			add(0, 0, n-1, scan.nextInt()-1, scan.nextInt()-1, scan.nextInt(), scan.nextInt());
		print(0, 0, n-1);
		
		pw.flush();
	}
	
	static int[] a;
	static int[][] tree;
	static boolean[] changed;

	static PrintWriter pw;
	
	static void print(int p, int s, int e) {
		if(s == e) {
			pw.print(tree[p][a[s]] + " ");
			return;
		}
		update(p);
		int m = (s + e) / 2;
		print(2*p+1, s, m);
		print(2*p+2, m+1, e);
	}
	
	static void update(int p) {
		if(!changed[p]) return;
		for(int i = 1; i <= 100; i++) {
			tree[2*p+1][i] = tree[p][tree[2*p+1][i]];
			tree[2*p+2][i] = tree[p][tree[2*p+2][i]];
		}
		for(int i = 1; i <= 100; i++) tree[p][i] = i;
		changed[2*p+1] = changed[2*p+2] = true;
		changed[p] = false;
	}
	
	static void add(int p, int s, int e, int l, int r, int x, int y) {
		if(e < l || r < s) return;
		if(l <= s && e <= r) {
			changed[p] = true;
			for(int i = 1; i <= 100; i++)
				if(tree[p][i] == x) tree[p][i] = y;
			return;
		}
		update(p);
		int m = (s + e) / 2;
		add(2*p+1, s, m, l, r, x, y);
		add(2*p+2, m+1, e, l, r, x, y);
	}
	
	static void build(int p, int s, int e) {
		for(int i = 1; i <= 100; i++)
			tree[p][i] = i;
		if(s == e) return;
		int m = (s + e) / 2;
		build(2*p+1, s, m);
		build(2*p+2, m+1, e);
	}
	
	
	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();
		}
	}
}