Weighted Union-Find

Problem Description

You are given $n$ variables $a_1, a_2, \dots, a_n$ whose values are initially unknown.

You must perform $q$ operations:

• 1 l r x: gives a clue that $a_l - a_r = x$. If this contradicts the known information, ignore this operation.
• 2 l r: answer $a_l - a_r$. If the current clues do not allow deducing the answer, ignore this operation.

Input Format

The first line contains two integers $n$ and $q$ ($1 \le n \le 2 \times 10^5$, $1 \le q \le 4 \times 10^5$).

The following $q$ lines each describe one operation. The input is encrypted as follows:

There is a variable $t$ initially $0$. After every query operation that is not ignored, $t$ becomes the absolute value of the answer, i.e. $|a_l - a_r|$. Each operation's input gives encrypted $l', r'$; the actual values are $l = (l' + t) \bmod n + 1$ and $r = (r' + t) \bmod n + 1$.

It is guaranteed that $1 \le l', r' \le n$ and $-10^9 \le x \le 10^9$.

Output Format

For each query operation that is not ignored, output its answer. If a query operation is ignored, output nothing for it.

Sample Input

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

Sample Output

2
-1