C. Serval и массивы Toxel
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Toxel любит массивы. Перед поездкой в Paldea Serval подарил ему массив $$$a$$$. Этот массив состоит из $$$n$$$ попарно различных элементов.

Чтобы получить больше массивов, Toxel выполнил $$$m$$$ операций с исходным массивом. $$$i$$$-й операцией он изменил $$$p_{i}$$$-й элемент $$$(i-1)$$$-го массива на $$$v_{i}$$$, в результате чего получился $$$i$$$-й массив (исходный массив $$$a$$$ имеет номер $$$0$$$). Во время изменений Toxel гарантировал, что элементы каждого массива по-прежнему попарно различны после каждой операции.

Наконец, Toxel получил $$$m+1$$$ массив и обозначил их как $$$A_{0}=a, A_{1},\ldots,A_{m}$$$. Для каждой пары $$$(i,j)$$$ ($$$0\le i<j\le m$$$), Toxel определил её значение как количество различных элементов в конкатенации $$$A_{i}$$$ и $$$A_{j}$$$. Теперь Toxel задается вопросом, какова сумма значений для всех пар массивов? Пожалуйста, помогите ему вычислить ответ.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$1\le a_{i}\le n+m$$$). Гарантируется, что все $$$a_i$$$ попарно различны.

Каждая из следующих $$$m$$$ строк каждого набора входных данных содержит два целых числа $$$p_{i}$$$ и $$$v_{i}$$$ ($$$1\le p_{i}\le n$$$, $$$1\le v_{i}\le n+m$$$) — позиция изменяемого элемента и его новое значение. Гарантируется, что элементы каждого массива по-прежнему попарно различны после каждой операции.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходят $$$2\cdot10^{5}$$$.

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

Для каждого набора входных данных выведите единственное целое число — сумму значений для всех пар массивов.

Пример
Входные данные
3
3 2
1 2 3
1 4
2 5
1 1
1
1 1
10 10
4 6 9 12 16 20 2 10 19 7
1 3
5 4
2 17
2 18
6 11
7 1
8 17
5 5
5 5
2 2
Выходные данные
13
1
705
Примечание

В первом наборе входных данных массив изменяется следующим образом: $$$[1,2,3]\to[\underline{4},2,3]\to[4,\underline{5},3]$$$.

Конкатенацией $$$0$$$-го массива $$$1$$$-го массива является $$$\require{cancel}[1,2,3,4,\cancel{2},\cancel{3}]$$$. Здесь есть $$$4$$$ различных элемента.

Конкатенацией $$$0$$$-го массива и $$$2$$$-го массива является $$$\require{cancel}[1,2,3,4,5,\cancel{3}]$$$. Здесь есть $$$5$$$ различных элементов.

Конкатенацией $$$1$$$-го массива и $$$2$$$-го массива является $$$\require{cancel}[4,2,3,\cancel{4},5,\cancel{3}]$$$. Здесь есть $$$4$$$ различных элемента.

Зачёркнутые элементы являются повторяющимися в массиве.

Таким образом, ответ равен $$$4+5+4=13$$$.

Во втором наборе входных данных обратите внимание, что массив может оставаться без изменений после операций.