Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

F. Vicky's Delivery Service
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 c1,c2,,ck satisfying the following properties:

  • For each i with 1ik1, the cities ci and ci+1 are connected by a road.
  • For each i with 1ik12, the roads connecting c2i with c2i1 and c2i+1 have the same color.

For example if k=5, the road between c1 and c2 must be the same color as the road between c2 and c3, and the road between c3 and c4 must be the same color as the road between c4 and c5.

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 (2n105, 1m,c,q105), 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 (1x,yn, 1zc), 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 (1x,yn, 1zc), meaning a road with color z appears between cities x and y;
  2. ? x y (1x,yn), meaning you should determine whether Vicky can make a delivery starting at city x and ending at city y. It is guaranteed that xy.

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.

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.