Problem: In a magical land there are n cities conveniently numbered 1, 2, ..., n. Some pairs of these cities are connected by magical colored roads. Magic is unstable, so at any time, new roads may appear between two cities.

Vicky the witch has been tasked with performing deliveries between some pairs of cities. However, Vicky is a beginner, so she can only complete a delivery if she can move from her starting city to her destination city through a double rainbow. A double rainbow is a sequence of cities c_1, c_2, ..., c_k satisfying the following properties:

  * For each i with 1 ≤ i ≤ k - 1, the cities c_i and c_{i + 1} are connected by a road. 
  * For each i with 1 ≤ i ≤ (k - 1)/(2), the roads connecting c_{2i} with c_{2i - 1} and c_{2i + 1} have the same color. 



For example if k = 5, the road between c_1 and c_2 must be the same color as the road between c_2 and c_3, and the road between c_3 and c_4 must be the same color as the road between c_4 and c_5.

Vicky has a list of events in chronological order, where each event is either a delivery she must perform, or appearance of a new road. Help her determine which of her deliveries she will be able to complete.

Input

The first line contains four integers n, m, c, and q (2 ≤ n ≤ 10^5, 1 ≤ m, c, q ≤ 10^5), denoting respectively the number of cities, the number of roads initially present, the number of different colors the roads can take, and the number of events.

Each of the following m lines contains three integers x, y, and z (1 ≤ x, y ≤ n, 1 ≤ z ≤ c), describing that there initially exists a bidirectional road with color z between cities x and y.

Then q lines follow, describing the events. Each event is one of the following two types: 

  1. + x y z (1 ≤ x, y ≤ n, 1 ≤ z ≤ c), meaning a road with color z appears between cities x and y; 
  2. ? x y (1 ≤ x, y ≤ n), meaning you should determine whether Vicky can make a delivery starting at city x and ending at city y. It is guaranteed that x ≠ y. 



It is guaranteed that at any moment, there is at most one road connecting any pair of cities, and that no road connects a city to itself. It is guaranteed that the input contains at least one event of the second type.

Output

For each event of the second type, print a single line containing "Yes" (without quotes) if the delivery can be made, or a single line containing "No" (without quotes) otherwise.

Example

Input


4 3 2 4
1 2 1
2 3 1
3 4 2
? 1 4
? 4 1
+ 3 1 2
? 4 1


Output


Yes
No
Yes

Note

The following picture corresponds to the sample.

<image>

For her first delivery, Vicky can use the sequence 1, 2, 3, 4 which is a double rainbow. However, she cannot complete the second delivery, as she can only reach city 3. After adding the road between cities 1 and 3, she can now complete a delivery from city 4 to city 1 by using the double rainbow 4, 3, 1.

Solution (in JAVA):

Solution:



import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.nio.charset.Charset;
import java.util.*;

public class CF1166F {
    public static void main(String[] args) throws Exception {
        boolean local = System.getProperty("ONLINE_JUDGE") == null;
        boolean async = false;

        Charset charset = Charset.forName("ascii");

        FastIO io = local ? new FastIO(new FileInputStream("D:\\DATABASE\\TESTCASE\\Code.in"), System.out, charset) : new FastIO(System.in, System.out, charset);
        Task task = new Task(io, new Debug(local));

        if (async) {
            Thread t = new Thread(null, task, "dalt", 1 << 27);
            t.setPriority(Thread.MAX_PRIORITY);
            t.start();
            t.join();
        } else {
            task.run();
        }

        if (local) {
            io.cache.append("\n\n--memory -- \n" + ((Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20) + "M");
        }

        io.flush();
    }

    public static class Task implements Runnable {
        final FastIO io;
        final Debug debug;
        int inf = (int) 1e8;
        int mod = (int) 1e9 + 7;

        public int mod(int val) {
            val %= mod;
            if (val < 0) {
                val += mod;
            }
            return val;
        }

        public int mod(long val) {
            val %= mod;
            if (val < 0) {
                val += mod;
            }
            return (int) val;
        }

        int bitAt(int x, int i) {
            return (x >> i) & 1;
        }

        int bitAt(long x, int i) {
            return (int) ((x >> i) & 1);
        }

        public Task(FastIO io, Debug debug) {
            this.io = io;
            this.debug = debug;
        }

        @Override
        public void run() {
            solve();
        }

        public void solve() {
            int n = io.readInt();
            int m = io.readInt();
            int c = io.readInt();
            int q = io.readInt();

            Node[] nodes = new Node[n + 1];
            for (int i = 1; i <= n; i++) {
                nodes[i] = new Node();
                nodes[i].id = i;
            }
            for (int i = 1; i <= m; i++) {
                Node a = nodes[io.readInt()];
                Node b = nodes[io.readInt()];
                int z = io.readInt();
                addEdge(a, b, z);
            }

            for (int i = 0; i < q; i++) {
                char cmd = io.readChar();
                Node a = nodes[io.readInt()];
                Node b = nodes[io.readInt()];
                if (cmd == '+') {
                    int z = io.readInt();
                    addEdge(a, b, z);
                } else {
                    if (b.find() == a.find() || a.find().nearby.contains(b)) {
                        io.cache.append("Yes\n");
                    } else {
                        io.cache.append("No\n");
                    }
                }
            }
        }

        static void addEdge(Node a, Node b, Integer c) {
            Node ac = a.edges.get(c);
            Node bc = b.edges.get(c);

            a.edges.put(c, b);
            b.edges.put(c, a);

            Node af = a.find();
            Node bf = b.find();

            if (af != bf) {
                af.nearby.add(b);
                bf.nearby.add(a);
            }

            Node.union(ac, bf);
            Node.union(bc, af);
        }
    }

    public static class Node {
        Map<Integer, Node> edges = new HashMap<>();
        Set<Node> nearby = new HashSet<>();

        Node p = this;
        int rank = 1;

        int id;

        Node find() {
            Node root = p;
            while (root.p != root) {
                root = root.p;
            }
            return root;
        }

        static void union(Node a, Node b) {
            if (a == null || b == null) {
                return;
            }
            a = a.find();
            b = b.find();
            if (a == b) {
                return;
            }
            if (a.rank <= b.rank) {
                Node tmp = a;
                a = b;
                b = tmp;
            }

            a.rank += b.rank;
            b.p = a;
            a.nearby = CollectionUtils.mergeHeuristically(a.nearby, b.nearby);
        }

        @Override
        public String toString() {
            return "" + id;
        }
    }

    public static class CollectionUtils {
        public static <E, T extends Collection<E>> T mergeHeuristically(T a, T b) {
            if (a.size() >= b.size()) {
                a.addAll(b);
                return a;
            } else {
                b.addAll(a);
                return b;
            }
        }
    }

    public static class FastIO {
        public final StringBuilder cache = new StringBuilder();
        private final InputStream is;
        private final OutputStream os;
        private final Charset charset;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 8);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastIO(InputStream is, OutputStream os, Charset charset) {
            this.is = is;
            this.os = os;
            this.charset = charset;
        }

        public FastIO(InputStream is, OutputStream os) {
            this(is, os, Charset.forName("ascii"));
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public long readLong() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            long val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public double readDouble() {
            boolean sign = true;
            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+';
                next = read();
            }

            long val = 0;
            while (next >= '0' && next <= '9') {
                val = val * 10 + next - '0';
                next = read();
            }
            if (next != '.') {
                return sign ? val : -val;
            }
            next = read();
            long radix = 1;
            long point = 0;
            while (next >= '0' && next <= '9') {
                point = point * 10 + next - '0';
                radix = radix * 10;
                next = read();
            }
            double result = val + (double) point / radix;
            return sign ? result : -result;
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

        public int readLine(char[] data, int offset) {
            int originalOffset = offset;
            while (next != -1 && next != '\n') {
                data[offset++] = (char) next;
                next = read();
            }
            return offset - originalOffset;
        }

        public int readString(char[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read();
            }

            return offset - originalOffset;
        }

        public int readString(byte[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (byte) next;
                next = read();
            }

            return offset - originalOffset;
        }

        public char readChar() {
            skipBlank();
            char c = (char) next;
            next = read();
            return c;
        }

        public void flush() {
            try {
                os.write(cache.toString().getBytes(charset));
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public boolean hasMore() {
            skipBlank();
            return next != -1;
        }
    }

    public static class Debug {
        private boolean allowDebug;

        public Debug(boolean allowDebug) {
            this.allowDebug = allowDebug;
        }

        public void assertTrue(boolean flag) {
            if (!allowDebug) {
                return;
            }
            if (!flag) {
                fail();
            }
        }

        public void fail() {
            throw new RuntimeException();
        }

        public void assertFalse(boolean flag) {
            if (!allowDebug) {
                return;
            }
            if (flag) {
                fail();
            }
        }

        private void outputName(String name) {
            System.out.print(name + " = ");
        }

        public void debug(String name, int x) {
            if (!allowDebug) {
                return;
            }

            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, long x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, double x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, int[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, long[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, double[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, Object x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, Object... x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.deepToString(x));
        }
    }

}