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

public class VickysDeliveryService {
    static HashMap<Integer, Integer>[] groups;
    static HashSet<Integer>[] p;
    static DSU dsu;
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        //Number of nodes
        int N = scanner.nextInt();
        //Number of initial edges
        int M = scanner.nextInt();
        //Number of different colors used (not used in the code)
        int C = scanner.nextInt();
        //Number of queries
        int Q = scanner.nextInt();
        //Disjoint set to keep track of portions of the graph that are connected by double edges
        dsu = new DSU(N);
        groups = new HashMap[N];
        //Set of items that can be reached from this node and from its neighbors
        p = new HashSet[N];
        //Initialization procedures
        for(int i = 0; i < N; i++) {
            groups[i] = new HashMap<>();
            p[i] = new HashSet<>();
            //Everyone is connected to themselves
            p[i].add(i);
        }
        for(int i = 0; i < M; i++) {
            //0 indexing
            int a = scanner.nextInt()-1;
            int b = scanner.nextInt()-1;
            //Used in a hashmap so dont care about indexing
            int c = scanner.nextInt();
            //update the sets
            update(a, b, c);
        }
        //Go through the queries
        while(Q-->0) {
            String type = scanner.next();
            //Adding an edge
            if (type.equals("+")) {
                int a = scanner.nextInt()-1;
                int b = scanner.nextInt()-1;
                int c = scanner.nextInt();
                update(a, b, c);
            }
            //Checking the connectivity
            else {
                int a = scanner.nextInt()-1;
                int b = scanner.nextInt()-1;
                if (p[dsu.find(a)].contains(b)) out.println("Yes");
                else out.println("No");
            }
        }
        out.flush();
    }
    
    public static void update(int a, int b, int c) {
        //If there are existing groups then we can merge with them
        //Existing groups implies there has been a previously added edge of color c
        //This means that we have a double colored edge and for everything in the same set, we can now connect
        if (groups[a].get(c)!= null) merge(groups[a].get(c), b);
        if (groups[b].get(c)!= null) merge(groups[b].get(c), a);
        //Add the fact that these are in, this is useless if above triggers, but harmless
        p[dsu.find(b)].add(a);
        p[dsu.find(a)].add(b);
        //update that we have seen some edge of this color for posterity
        groups[a].put(c,b);
        groups[b].put(c,a);
    }
    
    public static void merge(int a, int b) {
        //Want to merge smaller into larger and we designate a as the smaller one
        //Get the set reps
        int pa = dsu.find(a);
        int pb = dsu.find(b);
        //Swap if needed
        if (p[pa].size() > p[pb].size()) {
            int temp = pa;
            pa = pb;
            pb = temp;
        }
        //If not already in the same set
        if (dsu.union(pa, pb)) {
            //Copy over from the smaller into the larger
            //nlogn overall for the same reason dsu without path compression is
            for(int col: p[pa]) p[pb].add(col);
            //Clear the set
            p[pa].clear();
        }
    }
    
    public static class DSU {
        int[] parent;
        int nSets;
        public DSU(int ss) {
            nSets = ss;
            parent = new int[ss];
            for(int i = 0; i < ss; i++) {
                parent[i] = i;
            }
        }
        public int find(int a) {
            int prev = a;
            while(parent[a] != a) {
                a = parent[a];
            }
            compress(prev, a);
            return a;
        }
        public void compress(int a, int b) {
            while(parent[a] != b) {
                int temp = parent[a];
                parent[a] = b;
                a = temp;
            }
        }
        public boolean union(int a, int b) {
            if (a == b) return false;
            parent[a] = b;
            return true;
        }
    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}