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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Junior
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskG solver = new TaskG();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskG {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int ncolors = 100;
            int n = in.nextInt();
            Segtree s = new Segtree(n);
            for (int i = 0; i < n; ++i) {
                int x = in.nextInt();
                s.updatePoint(x, i);
            }
            int q = in.nextInt();
            while (q-- > 0) {
                int l = in.nextInt();
                int r = in.nextInt();
                int x = in.nextInt();
                int y = in.nextInt();
                s.updateColors(l - 1, r - 1, x, y);
            }
            int[] ans = new int[n];
            for (int i = 1; i <= ncolors; ++i) s.solve(i, ans);
            for (int i = 0; i < n; ++i) {
                if (i > 0) out.print(" ");
                out.print(ans[i]);
            }
            out.println();
        }

        class Node {
            Node l;
            Node r;
            int v;

            Node() {
                this.l = null;
                this.r = null;
                this.v = 0;
            }

            void update() {
                this.v = 0;
                if (this.l != null) this.v += this.l.v;
                if (this.r != null) this.v += this.r.v;
            }

        }

        class Segtree {
            Node[] root;
            int ncolors = 100;
            int n;

            public Segtree() {
                this.n = 500000;
                this.root = new Node[ncolors + 1];
            }

            public Segtree(int n) {
                this.n = n;
                this.root = new Node[ncolors + 1];
            }

            Node update(Node no, int l, int r, int i) {
                if (no == null) no = new Node();
                no.v++;
                if (l == r) return no;
                int md = (l + r) >> 1;
                if (i <= md) no.l = update(no.l, l, md, i);
                else no.r = update(no.r, md + 1, r, i);
                return no;
            }

            Pair<Node, Node> changeColors(Node nx, Node ny, int l, int r, int i, int j) {
                if ((r < i || l > j) || nx == null || (nx != null && nx.v == 0)) return Pair.makePair(nx, ny);
                if (ny == null) ny = new Node();
                if (l >= i && r <= j && ny.v == 0) {
                    ny = nx;
                    nx = null;
                    return Pair.makePair(nx, ny);
                }
                int md = (l + r) >> 1;
                Pair<Node, Node> sl = changeColors(nx.l, ny.l, l, md, i, j);
                nx.l = sl.first;
                ny.l = sl.second;
                Pair<Node, Node> sr = changeColors(nx.r, ny.r, md + 1, r, i, j);
                nx.r = sr.first;
                ny.r = sr.second;
                nx.update();
                ny.update();
                return Pair.makePair(nx, ny);
            }

            void updatePoint(int ir, int id) {
                root[ir] = update(root[ir], 0, n - 1, id);
            }

            void updateColors(int l, int r, int x, int y) {
                if (x == y) return;
                Pair<Node, Node> sol = changeColors(root[x], root[y], 0, n - 1, l, r);
                root[x] = sol.first;
                root[y] = sol.second;
            }

            void dfs(Node no, int cor, int l, int r, int[] ans) {
                if (no == null) return;
                if (no.v == 0) return;
                if (l == r) {
                    ans[l] = cor;
                    return;
                }
                int md = (l + r) >> 1;
                dfs(no.l, cor, l, md, ans);
                dfs(no.r, cor, md + 1, r, ans);
            }

            void solve(int ir, int[] ans) {
                dfs(root[ir], ir, 0, n - 1, ans);
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println() {
            writer.println();
        }

        public void close() {
            writer.close();
        }

        public void print(int i) {
            writer.print(i);
        }

    }

    static class Pair<U, V> implements Comparable<Pair<U, V>> {
        public final U first;
        public final V second;

        public static <U, V> Pair<U, V> makePair(U first, V second) {
            return new Pair<U, V>(first, second);
        }

        private Pair(U first, V second) {
            this.first = first;
            this.second = second;
        }


        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }

            Pair pair = (Pair) o;

            return !(first != null ? !first.equals(pair.first) : pair.first != null) &&
                    !(second != null ? !second.equals(pair.second) : pair.second != null);
        }


        public int hashCode() {
            int result = first != null ? first.hashCode() : 0;
            result = 31 * result + (second != null ? second.hashCode() : 0);
            return result;
        }


        public String toString() {
            return "(" + first + "," + second + ")";
        }

        @SuppressWarnings({"unchecked"})
        public int compareTo(Pair<U, V> o) {
            int value = ((Comparable<U>) first).compareTo(o.first);
            if (value != 0) {
                return value;
            }
            return ((Comparable<V>) second).compareTo(o.second);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

