You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一个魔法世界中，存在 $n$ 个城市，编号为 $1, 2, \dots, n$。部分城市之间通过带有颜色的魔法道路相互连接，且新的道路可能随时出现。

女巫 Vicky 需要在某些城市对之间进行配送任务，但她只能通过"双彩虹"路径完成配送。一个"双彩虹"路径是指满足以下条件的城市序列 $c_1, c_2, \dots, c_k$：

1. 对于每个 $i$（$1 \le i \le k-1$），城市 $c_i$ 和 $c_{i+1}$ 之间存在一条道路。
2. 对于每个 $i$（$1 \le i \le \left\lfloor \frac{k-1}{2} \right\rfloor$），连接 $c_{2i-1}$ 与 $c_{2i}$ 的道路颜色必须与连接 $c_{2i}$ 与 $c_{2i+1}$ 的道路颜色相同。

例如：

• 当 $k=5$ 时，$c_1$-$c_2$ 与 $c_2$-$c_3$ 的颜色必须相同，$c_3$-$c_4$ 与 $c_4$-$c_5$ 的颜色必须相同
• 当 $k=3$ 时，仅要求 $c_1$-$c_2$ 与 $c_2$-$c_3$ 的颜色相同

现在给定一系列按时间顺序排列的事件（新道路出现或配送请求），请判断每次配送请求是否能完成。

输入格式

第一行包含四个整数 $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：表示城市 $x$ 和 $y$ 之间新增一条颜色为 $z$ 的双向道路
2. ? x y：表示询问能否从城市 $x$ 通过"双彩虹"路径到达城市 $y$（保证 $x \neq y$）

输入保证：

• 任意时刻，任意一对城市之间最多只有一条道路
• 没有城市与自身相连
• 至少存在一个第二类事件

输出格式

对于每个第二类事件，输出一行：

• 若可以完成配送，输出 "Yes"
• 否则，输出 "No"

样例输入

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

样例输出

Yes
No
Yes

样例解释

初始道路网络中：

• 第一次查询（1→4）：路径 1-2-3-4 是双彩虹路径（1-2与2-3同色为1）
• 第二次查询（4→1）：无法形成有效双彩虹路径
• 添加3-1（颜色2）后，第三次查询（4→1）：路径 4-3-1 是双彩虹路径（3-4与3-1同色为2）

数据范围

本题总分为100分，采用多组测试数据，各测试点具体约束与分值如下：