Tree and Queries 16

There is a forest of $N$ vertices. The vertices are numbered from 1 to $N$. The initial forest has no edges.

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

Each of the next $Q$ lines contains three integers $t_i$, $a_i$, $b_i$. ($1 \le t_i \le 2$, $0 \le a_i, b_i < n$)

Consider an extra variable $last$, which starts at 0.

• If $t_i = 1$, the arguments are $u_i = ((a_i + last) \mod n) + 1$ and $v_i = ((b_i + last) \mod n) + 1$.
• If $t_i = 2$, the arguments are $u_i = ((a_i + last) \mod n) + 1$ and $k_i = ((b_i + last) \mod n)$. After computing the answer to this query, set $last$ to that answer.

For each query with $t_i = 2$, print the answer on its own line.