G. Ranges
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There are $$$n$$$ positions numbered from $$$1$$$ to $$$n$$$.

For every interval $$$[l,r]$$$, where $$$1 \le l \le r \le n$$$, there is a value associated with this interval. Values can be obtained in the following ways:

  • You may choose any interval $$$[l,r]$$$ and obtain its value directly. This costs one direct query.
  • If, for some $$$k$$$ with $$$l \le k \lt r$$$, you have already obtained the values for $$$[l,k]$$$ and $$$[k+1,r]$$$, then you may combine them and obtain the value for $$$[l,r]$$$ for free.

You may use the second operation any number of times. Values cannot be split: knowing the value for $$$[l,r]$$$ does not give you the values for its subintervals. There are no other ways to obtain values.

At any moment, there are $$$m$$$ required intervals. Your task is to determine the minimum number of direct queries needed to obtain the values for all required intervals.

After the initial configuration, $$$q$$$ modifications are performed. Each modification replaces one required interval with a new interval. You must output the answer for the initial configuration and after each modification.

Each configuration is considered independently. That is, for every output value, you need the minimum number of direct queries needed starting with no values already obtained.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \le n,m,q \le 2\cdot 10^5$$$) — the number of positions, the number of required intervals, and the number of modifications.

The next $$$m$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$). They describe the initial required intervals.

The next $$$q$$$ lines contain three integers $$$p$$$, $$$l$$$, and $$$r$$$ ($$$1 \le p \le m$$$, $$$1 \le l \le r \le n$$$). The required interval with index $$$p$$$ is replaced by $$$[l,r]$$$.

It is guaranteed that the sums of $$$n$$$, $$$m$$$, and $$$q$$$ over all test cases do not exceed $$$2\cdot 10^5$$$ each.

Output

For each test case, print $$$q+1$$$ integers, each on a separate line.

The first integer must be the minimum number of direct queries needed for the initial configuration. Then, after each modification, print the minimum number of direct queries needed for the current configuration.

Example
Input
3
5 3 3
1 2
3 5
2 4
3 1 5
1 2 2
2 4 5
3 2 2
1 3
1 3
2 1 1
1 2 3
15 8 8
15 15
13 14
10 10
8 12
8 15
15 15
15 15
14 14
1 3 3
8 10 12
4 12 14
6 13 15
6 7 11
8 10 12
3 1 3
5 11 12
Output
3
2
3
3
1
2
2
5
6
6
7
7
8
8
8
8
Note

In the first test case, initially at least $$$3$$$ direct queries are needed, so the answer is $$$3$$$.

After the first modification, the required intervals are $$$[1,2]$$$, $$$[3,5]$$$, and $$$[1,5]$$$. We can query $$$[1,2]$$$ and $$$[3,5]$$$ directly, and combine them to obtain $$$[1,5]$$$. Therefore, only $$$2$$$ direct queries are needed.

After the second modification, the required intervals are $$$[2,2]$$$, $$$[3,5]$$$, and $$$[1,5]$$$. At least $$$3$$$ direct queries are needed, so the answer is $$$3$$$.

After the third modification, the required intervals are $$$[2,2]$$$, $$$[4,5]$$$, and $$$[1,5]$$$. Again, at least $$$3$$$ direct queries are needed, so the answer is $$$3$$$.

In the second test case, the two initial required intervals are identical, so one direct query is enough and the answer is $$$1$$$.

After each modification, at least $$$2$$$ direct queries are needed, so the answers are both $$$2$$$.