У вас есть ориентированный граф, состоящий из \(n\) вершин. Каждое ориентированное ребро (дуга) помечено одной буквой. Первоначально, граф пустой.
Вам нужно обработать \(m\) запросов на нем. Каждый запрос одного из трех типов:
- «\(+\) \(u\) \(v\) \(c\)» — добавить дугу из \(u\) в \(v\) с меткой \(c\). Гарантируется, что в данный момент в графе нет дуги \((u, v)\);
- «\(-\) \(u\) \(v\)» — удалить дугу из \(u\) в \(v\). Гарантируется, что в данный момент в графе есть дуга \((u, v)\);
- «\(?\) \(k\)» — найти последовательность из \(k\) вершин \(v_1, v_2, \dots, v_k\) такую, что существуют и маршрут \(v_1 \to v_2 \to \dots \to v_k\), и маршрут \(v_k \to v_{k - 1} \to \dots \to v_1\), и если вы выпишите буквы вдоль обоих маршрутов, вы получите одинаковые строки. Вы можете посещать одни и те же вершины любое количество раз.
Выходные данные
Для каждого запроса третьего типа, выведите YES, если существует последовательность \(v_1, v_2, \dots, v_k\), описанная выше, иначе выведите NO.
Примечание
В первом запросе третьего типа \(k = 3\), и мы можем, например, выбрать последовательность \([1, 2, 3]\), так как \(1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3\) и \(3 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 1\).
Во втором запросе третьего типа \(k = 2\), и мы не можем выбрать такую последовательность \(p_1, p_2\), что дуги \((p_1, p_2)\) и \((p_2, p_1)\) имеют одинаковые метки.
В третьем запросе третьего типа, мы можем, например, выбрать последовательность \([1, 2, 3, 2, 1]\), где \(1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3 \xrightarrow{\text{d}} 2 \xrightarrow{\text{c}} 1\).