Имеется лес, состоящий из $N$ вершин. Вершины пронумерованы от 1 до $N$. Изначально в лесу нет рёбер.

Напишите программу, которая выполняет следующие запросы:

• 1 u v: Добавьте в лес ребро, соединяющее вершины $u$ и $v$. Гарантируется, что до вызова этого запроса в лесу не существовало пути между $u$ и $v$.
• 2 u k: Пусть $dist(u, v)$ обозначает длину кратчайшего пути между вершинами $u$ и $v$. Если вершины не соединены, то значение равно $\infty$. Верните количество вершин $v$, таких что $dist(u, v) = k$.

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

В первой строке даны два целых числа $N$, $Q$. ($1 \le N \le 100\,000$, $1 \le Q \le 200\,000$)

В следующих $Q$ строках даны три целых числа — информация о запросах $t_i$, $a_i$, $b_i$. ($1 \le t_i \le 2$, $0 \le a_i, b_i < n$)

Рассмотрим дополнительную переменную $last$. Изначально её значение равно 0.

• Если $t_i = 1$, то аргументы запроса $u_i$, $v_i$ определяются следующим образом: $u_i = ((a_i + last) \bmod n) + 1$, $v_i = ((b_i + last) \bmod n) + 1$.
• Если $t_i = 2$, то аргументы запроса $u_i$, $k_i$ определяются следующим образом: $u_i = ((a_i + last) \bmod n) + 1$, $k_i = ((b_i + last) \bmod n)$. После вычисления ответа на этот запрос обновите $last$ значением этого ответа.

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

Выведите ответы на запросы типа $t_i = 2$ по одному на каждой строке.

Примеры

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

7 9
1 0 6
1 4 3
1 0 5
1 1 2
1 3 1
1 4 5
2 2 3
2 2 1
2 0 0

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

1
2
1