Hay un bosque con $N$ vértices. Los vértices están numerados del $1$ al $N$. Inicialmente, el bosque no tiene aristas.

Escriba un programa que realice las siguientes consultas:

• 1 u v: Agrega al bosque una arista que conecta los dos vértices $u$ y $v$. Se garantiza que antes de que se llame a esta consulta, no existe ningún camino entre $u$ y $v$ en el bosque.
• 2 u k: Sea $dist(u, v)$ la longitud del camino más corto entre dos vértices $u$ y $v$. Si los dos vértices no están conectados, el valor es $\infty$. Devuelve la cantidad de vértices $v$ tales que $dist(u, v) = k$.

Entrada

En la primera línea se dan dos enteros $N, Q$. ($1 \le N \le 100\,000, 1 \le Q \le 200\,000$)

Luego, en $Q$ líneas se dan tres enteros $t_i, a_i, b_i$ con la información de las consultas. ($1 \le t_i \le 2, 0 \le a_i, b_i < n$)

Considere una variable adicional llamada $last$. Esta variable tiene inicialmente el valor $0$.

• Si $t_i = 1$, los argumentos de la consulta $u_i, v_i$ se definen como: $u_i = ((a_i + last) \bmod n) + 1$, $v_i = ((b_i + last) \bmod n) + 1$
• Si $t_i = 2$, los argumentos de la consulta $u_i, k_i$ se definen como: $u_i = ((a_i + last) \bmod n) + 1$, $k_i = ((b_i + last) \bmod n)$ Después de calcular la respuesta a esta consulta, actualice $last$ con el valor de dicha respuesta.

Salida

Imprima las respuestas de las consultas de tipo $t_i = 2$ en líneas separadas.

Ejemplos

Entrada

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

Salida

1
2
1