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 
//package com.company;


import java.util.*;
import java.io.*;


public class Main {
    static Random random = new Random();
    static class Treap {
        int key;
        long prio;
        Treap left;
        Treap right;
        int size;

        Treap(int key) {
            this.key = key;
            prio = random.nextLong();
            size = 1;
        }

        void update() {
            size = 1 + getSize(left) + getSize(right);
        }
    }

    static int getSize(Treap root) {
        return root == null ? 0 : root.size;
    }

    static class TreapPair {
        Treap left;
        Treap right;

        TreapPair(Treap left, Treap right) {
            this.left = left;
            this.right = right;
        }
    }

    static TreapPair split(Treap root, int minRight) {
        if (root == null)
            return new TreapPair(null, null);
        if (root.key >= minRight) {
            TreapPair leftSplit = split(root.left, minRight);
            root.left = leftSplit.right;
            root.update();
            leftSplit.right = root;
            return leftSplit;
        } else {
            TreapPair rightSplit = split(root.right, minRight);
            root.right = rightSplit.left;
            root.update();
            rightSplit.left = root;
            return rightSplit;
        }
    }

    static Treap merge(Treap left, Treap right) {
        if (left == null)
            return right;
        if (right == null)
            return left;
        // if (random.nextInt(left.size + right.size) < left.size) {
        if (left.prio > right.prio) {
            left.right = merge(left.right, right);
            left.update();
            return left;
        } else {
            right.left = merge(left, right.left);
            right.update();
            return right;
        }
    }

    static Treap insert(Treap root, int x) {
        TreapPair t = split(root, x);
        return merge(merge(t.left, new Treap(x)), t.right);
    }

    static Treap remove(Treap root, int x) {
        if (root == null) {
            return null;
        }
        if (x < root.key) {
            root.left = remove(root.left, x);
            root.update();
            return root;
        } else if (x > root.key) {
            root.right = remove(root.right, x);
            root.update();
            return root;
        } else {
            return merge(root.left, root.right);
        }
    }

    static int kth(Treap root, int k) {
        if (k < getSize(root.left))
            return kth(root.left, k);
        else if (k > getSize(root.left))
            return kth(root.right, k - getSize(root.left) - 1);
        return root.key;
    }

    static void print(Treap root, int[] res, int i) {
        if (root == null)
            return;
        print(root.left, res, i);
//        System.out.println(root.key);
        res[root.key] = i + 1;
        print(root.right, res, i);
    }

    static Treap union(Treap left, Treap right) {
        if (left == null) return right;
        if (right == null) return left;
        if (left.prio <= right.prio) return union(right, left);
        TreapPair sp = split(right, left.key);
        left.left = union(left.left, sp.left);
        left.right = union(left.right, sp.right);
        return left;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Treap[] treaps = new Treap[100];
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt() - 1;
            treaps[a] = merge(treaps[a], new Treap(i));
        }
        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt() - 1;
            int r = sc.nextInt();
            int x = sc.nextInt() - 1;
            int y = sc.nextInt() - 1;
            TreapPair xSmall = split(treaps[x], l);
            TreapPair xLarge = split(xSmall.right, r);
            treaps[x] = merge(xSmall.left, xLarge.right);
            treaps[y] = union(treaps[y], xLarge.left);
        }
        int[] res = new int[n];
        for (int i = 0; i < 100; i++) {
            print(treaps[i], res, i);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(res[i]).append(" ");
        }
        System.out.println(sb.toString());
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s){  br = new BufferedReader(new InputStreamReader(s));}

        public Scanner(FileReader s) throws FileNotFoundException {br = new BufferedReader(s);}

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

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

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

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

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

        public boolean ready() throws IOException {return br.ready();}
    }
}
