Дан неориентированный граф из \(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\) иначе.
Удачи!
Выходные данные
Выведите строку, состоящую из символов '0' и '1'. \(i\)-й символ должен быть равен ответу на \(i\)-й запрос второго типа. Таким образом, длина строки должна быть равна количеству запросов второго типа.
Примечание
Преобразованные запросы из первого примера:
- 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
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|