在一片神奇的土地上,有 $$$n$$$ 城市,方便地编号为 $$$1, 2, \dots, n$$$。其中一些城市通过神奇的彩色道路连接起来。魔法不稳定,因此两个城市之间随时都可能出现新的道路。
女巫维姬的任务是在一些城市之间进行送货。不过,Vicky 是新手,只有能够通过双彩虹从起始城市移动到目的地城市,才能完成配送。双彩虹是一系列城市 $$$c_1, c_2, \dots, c_k$$$ 满足以下属性:
- 对于每个 $$$i$$$ 且 $$$1 \le i \le k - 1$$$,城市 $$$c_i$$$ 和 $$$c_{i + 1}$$$ 通过道路连接。
- 对于每个 $$$i$$$ 和 $$$1 \le i \le \frac{k - 1}{2}$$$,连接 $$$c_{2i}$$$ 与 $$$c_{2i - 1}$$$ 和 $$$c_{2i + 1}$$$ 的道路具有相同的颜色。
例如,如果 $$$k = 5$$$,则 $$$c_1$$$ 和 $$$c_2$$$ 之间的道路必须与 $$$c_2$$$ 和 $$$c_3$$$ 之间的道路颜色相同,$$$c_3$$$ 和 $$$c_4$$$ 之间的道路必须与 $$$c_4$$$ 之间的道路颜色相同和$$$c_5$$$。
Vicky 有一个按时间顺序排列的事件列表,其中每个事件要么是她必须执行的交付,要么是一条新道路的出现。帮助她确定她能够完成哪些分娩。
输入
第一行包含四个整数 $$$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$$$ 和 $$$x$$$ 之间最初存在一条颜色为 $$$z$$$ 的双向道路$$$y$$$。
接下来是 $$$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$$$。
保证在任何时刻,至多有一条道路连接任意一对城市,并且没有道路将城市与其自身连接。保证输入至少包含一个第二类型的事件。
输出
对于第二种类型的每个事件,如果可以交付,则打印包含“是”(不带引号)的单行,否则打印包含“否”(不带引号)的单行。
示例
输入 #1
4 3 2 4 1 2 1 2 3 1 3 4 2 ? 1 4 ? 4 1 + 3 1 2 ? 4 1
输出 #1
Yes No Yes
注意
下图对应于示例。
对于第一次分娩,Vicky 可以使用序列 1、2、3、4,这是双彩虹。然而,她无法完成第二次送货,因为她只能到达城市$$$3$$$。添加城市$$$1$$$和$$$3$$$之间的道路后,她现在可以使用双彩虹4,3,1完成从城市$$$4$$$到城市$$$1$$$的配送。