F. Обменные запросы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы находитесь на рынке, где два торговца готовы обмениваться $$$n$$$ различными товарами. Каждый торговец представлен перестановкой, которая задает относительную ценность $$$n$$$ товаров для этого торговца. Обозначим эти две перестановки как $$$p$$$ и $$$s$$$. Если у вас есть товар $$$i$$$, вы можете обменять его на товар $$$j$$$, если либо $$$p_i \gt p_j$$$ (используя первого торговца), либо $$$s_i \gt s_j$$$ (используя второго торговца).

Скажем, что товар $$$i$$$ по крайней мере так же ценен, как товар $$$j$$$, если вы можете прийти на рынок с товаром $$$i$$$, сделать несколько (возможно, ни одного) обменов и получить товар $$$j$$$. Обратите внимание, что в любой момент у вас на руках будет ровно один товар. Можно считать, что у торговцев есть неограниченные запасы всех товаров.

Из-за постоянных изменений на рынке торговцы часто пересматривают свои взгляды на ценности товаров. Вам будет дано $$$q$$$ запросов; каждый из них представляет собой обмен позиций двух товаров в одной из перестановок. После каждого обновления вы должны вывести количество пар $$$(i, j)$$$ ($$$1 \le i, j \le n$$$), таких что товар $$$i$$$ по крайней мере так же ценен, как товар $$$j$$$.

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

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

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

Следующие две строки содержат изначальные перестановки $$$p$$$ и $$$s$$$.

Следующие $$$q$$$ строк содержат по три целых числа $$$tp$$$, $$$i$$$, $$$j$$$ ($$$tp \in \{ 1, 2 \}$$$, $$$1 \le i, j \le n$$$, $$$i \ne j$$$). Если $$$tp=1$$$, обменяйте $$$p_i$$$ и $$$p_j$$$. Если $$$tp=2$$$, обменяйте $$$s_i$$$ и $$$s_j$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$, и сумма $$$q$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных выведите $$$q$$$ строк, $$$k$$$-я из которых содержит одно целое число — количество пар $$$(i, j)$$$, таких что товар $$$i$$$ по крайней мере так же ценен, как товар $$$j$$$, после первых $$$k$$$ обновлений.

Пример
Входные данные
2
3 3
1 2 3
3 2 1
2 1 3
2 1 3
1 1 2
4 2
3 2 4 1
3 1 4 2
1 1 3
2 1 3
Выходные данные
6
9
9
12
11
Примечание

В первом наборе входных данных после первого обновления обе перестановки являются идентичными перестановками, поэтому единственными допустимыми парами являются $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(3, 1)$$$, $$$(3, 2)$$$ и $$$(3, 3)$$$. После второго обновления возможно получить любой товар, начиная с любого товара. Например, вы можете получить товар $$$3$$$ из товара $$$1$$$, используя второго торговца, так как $$$s_1 = 3 \gt 1 = s_3$$$. После третьего обновления все еще возможно получить любой товар, начиная с любого товара. Например, если вы начинаете с товаром $$$2$$$ и хотите получить товар $$$1$$$, вы можете сначала обменять ваш товар $$$2$$$ на товар $$$3$$$, используя второго торговца, а затем обменять товар $$$3$$$ на товар $$$1$$$, используя первого торговца.