F. Задача с обязательными онлайн-запросами
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный граф из $$$n$$$ вершин и без ребер. Вершины пронумерованы от $$$1$$$ до $$$n$$$.

Необходимо ответить на запросы к нему. Пусть $$$last$$$ будет ответом на предыдущий запрос второго типа (или $$$0$$$, если таких запросов еще не было). Тогда запросы следующие:

  • $$$1~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — добавить неориентированное ребро между вершинами $$$(x + last - 1)~mod~n + 1$$$ и $$$(y + last - 1)~mod~n + 1$$$, если такого в графе нет, а иначе удалить его;
  • $$$2~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — проверить, что существует путь между вершинами $$$(x + last - 1)~mod~n + 1$$$ и $$$(y + last - 1)~mod~n + 1$$$, который проходит только через существующие ребра, и выставить $$$last$$$ значение $$$1$$$, если есть, и $$$0$$$ иначе.

Удачи!

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

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$) — количество вершин в графе и количество запросов, соответственно.

В каждой из следующих $$$m$$$ строк записан запрос одного из выше приведенных типов. Гарантируется, что есть хотя бы один запрос второго типа.

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

Выведите строку, состоящую из символов '0' и '1'. $$$i$$$-й символ должен быть равен ответу на $$$i$$$-й запрос второго типа. Таким образом, длина строки должна быть равна количеству запросов второго типа.

Примеры
Входные данные
5 9
1 1 2
1 1 3
2 3 2
1 2 4
2 3 4
1 2 4
2 3 4
1 1 3
2 4 3
Выходные данные
1010
Входные данные
3 9
1 1 2
1 2 3
1 3 1
2 1 3
1 3 2
2 2 3
1 1 2
2 1 2
2 1 2
Выходные данные
1101
Примечание

Преобразованные запросы из первого примера:

  • 1 1 2
  • 1 1 3
  • 2 3 2
  • 1 3 5
  • 2 4 5
  • 1 2 4
  • 2 3 4
  • 1 2 4
  • 2 5 4

Преобразованные запросы из второго примера:

  • 1 1 2
  • 1 2 3
  • 1 3 1
  • 2 1 3
  • 1 1 3
  • 2 3 1
  • 1 2 3
  • 2 2 3
  • 2 1 2