There is a forest consisting of $N$ vertices. The vertices are numbered from $1$ to $N$. Initially, there are no edges in the forest.

Write a program that processes the following queries:

• 1 u v: Add an edge connecting two vertices $u$ and $v$ to the forest. It is guaranteed that before this query is called, there is no path between $u$ and $v$ in the forest.
• 2 u k: Let $dist(u, v)$ be the length of the shortest path between two vertices $u$ and $v$. If the two vertices are not connected, the value is $\infty$. Return the number of vertices $v$ such that $dist(u, v) = k$.

Input

First line contains two integers $N, Q$. ($1 \le N \le 100\,000$, $1 \le Q \le 200\,000$)

Next $Q$ lines each contain three integers $t_i, a_i, b_i$ representing a query. ($1 \le t_i \le 2$, $0 \le a_i, b_i < n$)

Consider an additional variable $last$. This variable initially has the value $0$.

• When $t_i = 1$, the arguments of the query $u_i, v_i$ are defined as: $u_i = ((a_i + last) \bmod n) + 1$, $v_i = ((b_i + last) \bmod n) + 1$.
• When $t_i = 2$, the arguments of the query $u_i, k_i$ are defined as: $u_i = ((a_i + last) \bmod n) + 1$, $k_i = ((b_i + last) \bmod n)$. After computing the answer to this query, update $last$ to that answer.

Output

Output the answers to queries of type $t_i = 2$ on separate lines.

Examples

Input 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

Output 1

1
2
1