G. Отрезки
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ позиций, пронумерованных от $$$1$$$ до $$$n$$$.

С каждым отрезком $$$[l,r]$$$, где $$$1 \le l \le r \le n$$$, связано некоторое значение. Значения можно получить следующими способами:

  • Можно выбрать любой отрезок $$$[l,r]$$$ и получить его значение напрямую. Это стоит одного прямого запроса.
  • Если для некоторого $$$k$$$, удовлетворяющего $$$l \le k \lt r$$$, вы уже получили значения для $$$[l,k]$$$ и $$$[k+1,r]$$$, их можно объединить и бесплатно получить значение для $$$[l,r]$$$.

Вторую операцию можно использовать любое количество раз. Значения нельзя разделять: знание значения для $$$[l,r]$$$ не даёт значений его подотрезков. Других способов получить значения нет.

В каждый момент есть $$$m$$$ требуемых отрезков. Ваша задача — определить минимальное количество прямых запросов, необходимое для получения значений всех требуемых отрезков.

После исходной конфигурации выполняется $$$q$$$ изменений. Каждое изменение заменяет один требуемый отрезок новым. Требуется вывести ответ для исходной конфигурации и после каждого изменения.

Каждая конфигурация рассматривается независимо. Иными словами, для каждого выводимого значения требуется минимальное количество прямых запросов при условии, что изначально никакие значения не получены.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1 \le n,m,q \le 2\cdot 10^5$$$) — количество позиций, количество требуемых отрезков и количество изменений.

Следующие $$$m$$$ строк содержат по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$). Они описывают исходные требуемые отрезки.

Следующие $$$q$$$ строк содержат по три целых числа $$$p$$$, $$$l$$$ и $$$r$$$ ($$$1 \le p \le m$$$, $$$1 \le l \le r \le n$$$). Требуемый отрезок с индексом $$$p$$$ заменяется на $$$[l,r]$$$.

Гарантируется, что суммы $$$n$$$, $$$m$$$ и $$$q$$$ по всем наборам входных данных не превосходят $$$2\cdot 10^5$$$ каждая.

Выходные данные

Для каждого набора входных данных выведите $$$q+1$$$ целых чисел, каждое в отдельной строке.

Первое число должно быть равно минимальному количеству прямых запросов, необходимых для исходной конфигурации. Затем после каждого изменения выведите минимальное количество прямых запросов, необходимых для текущей конфигурации.

Пример
Входные данные
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
Выходные данные
3
2
3
3
1
2
2
5
6
6
7
7
8
8
8
8
Примечание

В первом наборе входных данных изначально требуется хотя бы $$$3$$$ прямых запроса, поэтому ответ равен $$$3$$$.

После первого изменения требуемыми являются отрезки $$$[1,2]$$$, $$$[3,5]$$$ и $$$[1,5]$$$. Можно напрямую запросить $$$[1,2]$$$ и $$$[3,5]$$$, а затем объединить их, чтобы получить $$$[1,5]$$$. Поэтому требуется всего $$$2$$$ прямых запроса.

После второго изменения требуемыми являются отрезки $$$[2,2]$$$, $$$[3,5]$$$ и $$$[1,5]$$$. Требуется хотя бы $$$3$$$ прямых запроса, поэтому ответ равен $$$3$$$.

После третьего изменения требуемыми являются отрезки $$$[2,2]$$$, $$$[4,5]$$$ и $$$[1,5]$$$. Снова требуется хотя бы $$$3$$$ прямых запроса, поэтому ответ равен $$$3$$$.

Во втором наборе входных данных два исходных требуемых отрезка совпадают, поэтому достаточно одного прямого запроса, и ответ равен $$$1$$$.

После каждого изменения требуется хотя бы $$$2$$$ прямых запроса, поэтому оба ответа равны $$$2$$$.