问题 J: The Mine of Abyss

Recently, a huge mine with $n$ crystals under deep ground has been detected in Byteland. The crystals are labeled by $1,2,\dots ,n$. The weight of each crystal is not confirmed, but a range can be estimated. Specifically, the weight of the $i$-th crystal is an integer within the range [ai,bi].

You are the analyzer of this mine. You will be given $q$ operations, each operation is one of the following:

• ''$\text{1 k a b}$'' ($1\le k\le n$, $1\le a\le b\le 1e9$): The $k$-th crystal is re-scanned. The new report shows its weight is an integer within the range $[a,b]$. The previous range is useless now.
• ''$\text{2 l r}$'' ($1\le l\le r\le n$): Assume some (maybe none or maybe all) crystals indexed in $[l,r]$ are unearthed, let's measure their total weight, how many possible total weights may we get?

The first line contains a single integer $T$ ($1\le T\le 5$), the number of test cases. For each test case:

The first line contains two integers $n$ and $q$ ($1\le n,q\le 50,000$), denoting the number of crystals and the number of operations.

In the next $n$ lines, the $i$-th line contains two integers ai and bi (1≤ai,bi≤1e9), denoting the weight range of the $i$-th crystal.

Each of the next $q$ lines describes an operation in formats described in the statement above.

It is guaranteed that all the values of ai,bi,a,b are chosen uniformly at random from integers in their corresponding ranges. The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.

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

3
5
9
13