F. Служба доставки Вики
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В одной волшебной стране ровно $$$n$$$ городов, пронумерованных $$$1, 2, \dots, n$$$. Некоторые пары городов соединены волшебными цветными дорогами. Волшебство непостоянно, поэтому иногда между городами возникают новые дороги.

Работа ведьмы Вики — доставлять посылки из одних городов в другие. Вики — новичок, поэтому она может выполнить доставку, только если существует двойной радужный путь из начального города в конечный. Двойным радужным путем называется последовательность городов $$$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$$$.

У Вики есть список событий в хронологическом порядке. Каждое событие — это либо доставка, которую она должна выполнить, либо появление новой дороги. Помогите ей определить, какие доставки она сможет выполнить.

Входные данные

Первая строка содержит четыре целых числа $$$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$$$), описывающих, что изначально существует двунаправленная дорога цвета $$$z$$$ между городами $$$x$$$ и $$$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$$$): означает, что вы должны определить, может ли Вики совершить доставку из города $$$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, 2, 3, 4, который является двойным радужным. Вторую доставку нельзя осуществить, так как лучшее, что может сделать Вики — добраться до города $$$3$$$. После добавления новой дороги между городами $$$1$$$ и $$$3$$$, Вики может добраться из города $$$4$$$ в город $$$1$$$ по двойному радужному пути 4, 3, 1.