Рисуем и вытираем
Рисуем и вытираем
Наш хороший знакомый Микки-Маус имеет лес из N вершин. Микки-Маус хочет выполнять над этими вершинами следующие 3 операции:
0 - Нарисовать ребро между двумя вершинами.1 - Стереть последние X нарисованных рёбер.2 - Дать ответ на вопрос, существует ли произвольный путь между двумя вершинами.
Помогите Микки-Маусу быстро отвечать на 3-тью оперцию.
Input data
В первой строке задано N (1 ≤ N ≤ 10^5) – количество вершин, в следующей строяке число Q (1 ≤ Q ≤ 10^5) – количество запросов трёх типов. В процессе обработки необходимо поддерживать число p, вначале оно равно 0. Каждая запись типа 0 и 2 задаётся тройкой чисел 0 x_i y_i, для получения номеров вершин, между которыми нужно нарисовать ребро или найти путь, задаётся следующим образом:
A_i = ((x_i + p + i) mod N) + 1, B_i = ((y_i + 1 – p + i) mod N) + 1 (1 ≤ A_i, x_i, B_i, y_i ≤ N).
Запросы типа 1 задаются парой чисел 1 x_i. x_i_{ } не больше, чем количество нарисованных на данный момент рёбер. После каждого запроса типа 2, p присваивается результат (YES = 1, NO = 0).
Output data
Для каждого запроса типа 2 вывести "YES" (без кавычек), если существует путь между двумя вершинами, иначе "NO" (без кавычек), если пути не существует.
Examples
6 11 0 1 4 0 5 6 0 3 1 2 4 5 0 4 4 2 4 2 1 1 2 4 1 0 4 2 0 3 5 2 6 2
NO YES YES YES