CF1166F.Vicky's Delivery Service

In a magical land there are $n$ cities conveniently numbered $1, 2, \dots, 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, \dots, c_k$ satisfying the following properties:

• For each $i$ with $1 \le i \le k - 1$, the cities $c_i$ and $c_{i + 1}$ are connected by a road.
• For each $i$ with $1 \le i \le \frac{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.

在一个神奇的国度中，有 $n$ 座城市，编号分别为 $1, 2, \dots, n$。这些城市中的某些对之间由带有魔法色彩的道路相连。由于魔法不稳定，任意时刻都可能在两座城市之间新出现一条道路。

女巫薇姬（Vicky）被委派在若干对城市之间执行运输任务。然而，薇姬尚属新手，她仅当能从起始城市到达目标城市、且所经路径构成一道“双彩虹”（double rainbow）时，才能完成一次运输任务。“双彩虹”是指一个城市序列 $c_1, c_2, \dots, c_k$，满足以下性质：

• 对每个满足 $1 \le i \le k - 1$ 的 $i$，城市 $c_i$ 与 $c_{i + 1}$ 之间存在一条道路；
• 对每个满足 $1 \le i \le \frac{k - 1}{2}$ 的 $i$，连接 $c_{2i}$ 与 $c_{2i - 1}$ 的道路和连接 $c_{2i}$ 与 $c_{2i + 1}$ 的道路颜色相同。

例如，若 $k = 5$，则 $c_1$ 与 $c_2$ 之间的道路颜色必须等于 $c_2$ 与 $c_3$ 之间的道路颜色，且 $c_3$ 与 $c_4$ 之间的道路颜色必须等于 $c_4$ 与 $c_5$ 之间的道路颜色。

薇姬拥有一份按时间顺序排列的事件列表，其中每个事件要么是一次她必须完成的运输任务，要么是一条新道路的出现。请帮她判断：她能完成哪些运输任务？

The first line contains four integers $n$, $m$, $c$, and $q$ ($2 \le n \le 10^5$, $1 \le m, c, q \le 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 \le x, y \le n$, $1 \le z \le 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 \le x, y \le n$, $1 \le z \le c$), meaning a road with color $z$ appears between cities $x$ and $y$;
2. ? x y ($1 \le x, y \le 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 \neq 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.

第一行包含四个整数 $n$、$m$、$c$ 和 $q$（$2 \le n \le 10^5$，$1 \le m, c, q \le 10^5$），分别表示城市的数量、初始存在的道路数量、道路可取的颜色种类数，以及事件的数量。

接下来的 $m$ 行，每行包含三个整数 $x$、$y$ 和 $z$（$1 \le x, y \le n$，$1 \le z \le c$），表示城市 $x$ 与城市 $y$ 之间初始存在一条颜色为 $z$ 的双向道路。

随后是 $q$ 行，描述各个事件。每个事件属于以下两种类型之一：

1. + x y z（$1 \le x, y \le n$，$1 \le z \le c$），表示在城市 $x$ 与城市 $y$ 之间新增一条颜色为 $z$ 的道路；
2. ? x y（$1 \le x, y \le n$），表示你需要判断 Vicky 是否能从城市 $x$ 出发、最终抵达城市 $y$ 完成配送任务。保证 $x \neq y$。

保证在任意时刻，任意两个城市之间至多只存在一条道路，且不存在连接某城市到其自身的道路。保证输入中至少包含一个第二类事件。

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.

对于每个第二类事件，如果可以完成配送，则输出一行“Yes”（不带引号）；否则，输出一行“No”（不带引号）。

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.

下图对应样例。

对于她的第一次配送，Vicky 可以使用序列 1, 2, 3, 4，这是一个双彩虹序列。然而，她无法完成第二次配送，因为她只能到达城市 $3$。在添加了城市 $1$ 与城市 $3$ 之间的道路后，她现在可以通过双彩虹序列 4, 3, 1 完成从城市 $4$ 到城市 $1$ 的配送。