带权并查集

题目描述

给你 $n$ 个变量 $a_1, a_2, \dots, a_n$，一开始不知道这些数是多少。

你要执行$q$次操作。

• 1 l r x，给你一条线索，表示 $a_l - a_r = x$，如果与已知条件矛盾，那么忽略这次操作。
• 2 l r回答 $a_l - a_r$，如果现在的线索无法推出答案，那么忽略这次操作。

输入格式

第一行两个整数 $n, q(1\leq n \leq 2\times 10^5, 1\leq q \leq 4\times 10^5)$。

接下来 $q$ 行，每行一个操作，输入会按如下方式进行加密。

有一个变量 $t$，一开始 $t = 0$，每次未被忽略的查询操作之后，$t$ 会变成答案的绝对值，也就是 $|a_l - a_r|$。每次操作输入的是加密后的 $l', r'$，实际上的 $l = (l' + t) \bmod n + 1, r = (r' + t) \bmod n + 1$。

保证 $1\leq l', r'\leq n, -10^9 \leq x \leq 10^9$。

输出格式

对于每个未被忽略的查询操作，输出答案。如果查询操作被忽略了，那么不用输出任何东西。

样例输入

3 5
1 1 2 1
2 1 3
1 2 3 1
2 1 3
2 1 3

样例输出

2
-1