Mamy las złożony z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$. Początkowo las nie zawiera żadnych krawędzi.

Napisz program wykonujący następujące zapytania:

• 1 u v: Dodaj do lasu krawędź łączącą dwa wierzchołki $u$ i $v$. Przed wywołaniem tego zapytania gwarantowane jest, że w lesie nie istnieje ścieżka między $u$ a $v$.
• 2 u k: Niech $dist(u, v)$ oznacza długość najkrótszej ścieżki między wierzchołkami $u$ i $v$. Jeśli dwa wierzchołki nie są połączone, wartość ta wynosi $\infty$. Zwróć liczbę wierzchołków $v$ takich, że $dist(u, v) = k$.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $N, Q$ ($1 \le N \le 100\,000$, $1 \le Q \le 200\,000$).

Następnie w $Q$ wierszach podane są trzy liczby całkowite $t_i, a_i, b_i$ opisujące zapytania ($1 \le t_i \le 2$, $0 \le a_i, b_i < n$).

Rozważmy dodatkową zmienną $last$. Początkowo ma ona wartość $0$.

• Gdy $t_i = 1$, argumenty zapytania $u_i, v_i$ są zdefiniowane następująco: $u_i = ((a_i + last) \bmod n) + 1$, $v_i = ((b_i + last) \bmod n) + 1$.
• Gdy $t_i = 2$, argumenty zapytania $u_i, k_i$ są zdefiniowane następująco: $u_i = ((a_i + last) \bmod n) + 1$, $k_i = ((b_i + last) \bmod n)$. Po obliczeniu odpowiedzi na to zapytanie aktualizujemy $last$ na tę odpowiedź.

Wyjście

Dla każdego zapytania typu $t_i = 2$ wypisz odpowiedź w osobnym wierszu.

Przykład

Wejście 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

Wyjście 1

1
2
1