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 
/**
 * Created by Aminul on 7/24/2018.
 */

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Random;

public class CF911G_2 {
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt();
        arr = new byte[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = (byte)in.nextInt();
        }

        int q = in.nextInt();

        SegTree seg = new SegTree(n);

        for (int i = 1; i <= q; i++) {
            int l = in.nextInt(), r = in.nextInt(), x = in.nextInt(), y = in.nextInt();
            seg.update(l, r, x, y, i);
        }

        seg.buildArray();

        for(int i = 1; i <= n; i++){
            pw.print(arr[i] + " ");
        }
        pw.println();

        pw.close();
    }

    static byte seg[][], arr[];
    static boolean changed[];

    static class SegTree{
        int n;
        SegTree(int N){
            n =  N;
            seg = new byte[4*n][101];
            changed = new boolean[4*n];
            for (int i = 0; i < 4*n; i++) {
                for(byte j = 1; j <= 100; j++){
                    seg[i][j] = j;
                }
            }
        }

        void pushDown(int p, int l, int r){
            if(!changed[p]) return;
            for(byte i = 1; i <= 100; i++){
                seg[l][i] = seg[p][seg[l][i]];
                seg[r][i] = seg[p][seg[r][i]];
            }
            for (byte i = 1; i <= 100; i++) {
                seg[p][i] = i;
            }
            changed[l] = changed[r] = true;
            changed[p] = false;
        }

        void update(int l, int r, int x, int y, int t){
            update(1, 1, n, l, r, (byte)x, (byte)y, t);
        }

        void update(int p, int s, int e, int a, int b, byte x, byte y, int t){
            if(s >= a && e <= b){
                for (int i = 1; i <= 100; i++) {
                    if(seg[p][i] == x){
                        seg[p][i] = y;
                    }
                    changed[p] = true;
                }
                return;
            }
            if(s > e || s > b || e < a) return;
            int m = (s + e) / 2, l = 2*p, r = l+1;
            pushDown(p, l, r);
            update(l, s, m, a, b, x, y, t);
            update(r, m+1, e, a, b, x, y, t);
        }

        void buildArray(){
            buildArray(1, 1, n);
        }

        void buildArray(int p, int s, int e){
            if(s == e){
                arr[s] = seg[p][arr[s]];
                return;
            }
            if(s > e) return;
            int m = (s + e) / 2, l = 2*p, r = l+1;
            pushDown(p, l, r);
            buildArray(l, s, m);
            buildArray(r, m+1, e);
        }
    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
        static final int ints[] = new int[128];

        public FastReader(InputStream is){
            for(int i='0';i<='9';i++) ints[i]=i-'0';
            this.is = is;
        }

        public int readByte(){
            if(lenbuf == -1)throw new InputMismatchException();
            if(ptrbuf >= lenbuf){
                ptrbuf = 0;
                try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
                if(lenbuf <= 0)return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        public int skip() {
            int b;
            while((b = readByte()) != -1 && isSpaceChar(b));
            return b;
        }

        public String next(){
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt(){
            int num = 0, b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
       /* public char nextChar() {
            return (char)skip();
        }*/

        public char[] next(int n){
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while(p < n && !(isSpaceChar(b))){
                buf[p++] = (char)b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        /*private char buff[] = new char[1005];
        public char[] nextCharArray(){
            int b = skip(), p = 0;
            while(!(isSpaceChar(b))){
                buff[p++] = (char)b;
                b = readByte();
            }
            return Arrays.copyOf(buff, p);
        }*/
    }
}