트리와 쿼리 16

N개의 정점으로 이루어진 포레스트가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 초기 포레스트에는 간선이 없다.

첫 번째 줄에 두 정수 $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$)

초기값이 0인 추가 변수 $last$를 생각하자.

• $t_i = 1$이면 인자는 $u_i = ((a_i + last) \mod n) + 1$, $v_i = ((b_i + last) \mod n) + 1$이다.
• $t_i = 2$이면 인자는 $u_i = ((a_i + last) \mod n) + 1$, $k_i = ((b_i + last) \mod n)$이다. 이 쿼리의 답을 계산한 뒤, $last$를 그 답으로 갱신한다.

$t_i = 2$인 쿼리마다 답을 한 줄에 하나씩 출력한다.