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.*;
import java.util.*;

public class A{

	static int []a;
	static PrintWriter out=new PrintWriter(System.out);
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		
		int n=sc.nextInt();
		a=new int [n];
		SegmentTree tree=new SegmentTree(n);
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt()-1;
		int q=sc.nextInt();
		while(q-->0) {
			tree.update(sc.nextInt()-1, sc.nextInt()-1, sc.nextInt()-1, sc.nextInt()-1);
		}
		tree.query();
		out.close();

	}
	static class SegmentTree
	{
		
		int[][]tree;
		
		static int MAX=100;
		int n;
		SegmentTree(int n){
			this.n=n;
			
			
			tree=new int[4*n][MAX];
			build(1,0,n-1);
		}
		void query() {
			query(1,0,n-1);
		}
		void query(int node,int tl,int tr) {
			if(tl==tr) {
				
				out.println(tree[node][a[tl]]+1);
				
			}
			else
			{
				int mid=tl+tr>>1,left=node<<1,right=left|1;
				propagate(node, left, right);
				query(left,tl,mid);
				query(right,mid+1,tr);
			}
		}
		void build(int node,int tl,int tr) {
			for(int i=0;i<100;i++) {
				tree[node][i]=i;
			}
			
			if(tl!=tr) {
				int mid=tl+tr>>1;
				build(node<<1,tl,mid);
				build(node<<1|1,mid+1,tr);
			}
			
		}
		void update(int l,int r,int from,int to) {
			if(from==to)
				return;
			update(1,0,n-1,l,r,from,to);
		}
		void update(int node,int tl,int tr,int l,int r,int from,int to) {
			if(r<tl || tr<l)
				return ;
			if(tl>=l && tr<=r) {
				for(int i=0;i<MAX;i++)
					if(tree[node][i]==from)
						tree[node][i]=to;
				return;
			}
			int mid=tl+tr>>1,left=node<<1,right=left|1;
			propagate(node, left, right);
			update(left,tl,mid,l,r,from,to);
			update(right,mid+1,tr,l,r,from,to);
			
			
		}
		void propagate(int node,int left,int right) {
			for(int i=0;i<MAX;i++) {
				int x;
				x=tree[left][i];
				tree[left][i]=tree[node][x];
				x=tree[right][i];
				tree[right][i]=tree[node][x];
			}
			for(int i=0;i<MAX;i++)
				tree[node][i]=i;
		}
		
	}
	
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		Scanner(String fileName) throws FileNotFoundException{
			br=new BufferedReader(new FileReader(fileName));
		}
		String next() throws IOException {
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		String nextLine() throws IOException {
			return br.readLine();
		}
		int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
		long nextLong()  throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}
}