You are at a marketplace and there are two traders who are willing to trade on $$$n$$$ different items. Each trader is represented by a permutation that signifies the relative value of the $$$n$$$ items for that trader. Let's denote those two permutations $$$p$$$ and $$$s$$$. If you have an item $$$i$$$, you can trade it for an item $$$j$$$ if either $$$p_i \gt p_j$$$ (using the first trader) or $$$s_i \gt s_j$$$ (using the second trader).

We say that an item $$$i$$$ is at least as valuable as an item $$$j$$$ if you can come to the marketplace with item $$$i$$$, make some (possibly none) trades, and get item $$$j$$$. Note that at any moment, you will have exactly one item on hand. Assume that the traders have infinite supplies of any item.

Due to the never-ending updates in the market, traders will often reevaluate their views on the item values. You will be given $$$q$$$ queries; each is a swap in one of the permutations. After every update, you should print the number of pairs $$$(i, j)$$$ ($$$1 \le i, j \le n$$$) such that item $$$i$$$ is at least as valuable as item $$$j$$$.

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 two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$).

The next two lines contain the initial permutations $$$p$$$ and $$$s$$$.

The following $$$q$$$ lines each contain three integers $$$tp$$$, $$$i$$$, $$$j$$$ ($$$tp \in \{ 1, 2 \}$$$, $$$1 \le i, j \le n$$$, $$$i \ne j$$$). If $$$tp=1$$$, swap $$$p_i$$$ with $$$p_j$$$. If $$$tp=2$$$, swap $$$s_i$$$ with $$$s_j$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output $$$q$$$ lines, the $$$k$$$-th of them containing a single integer — the number of pairs $$$(i, j)$$$ such that item $$$i$$$ is at least as valuable as item $$$j$$$ after the first $$$k$$$ updates.

Note

In the first test case, after the first update, both permutations are the identity permutations and thus the only valid pairs are $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(3, 1)$$$, $$$(3, 2)$$$, and $$$(3, 3)$$$. After the second update, it is possible to get any item starting with any item. For instance, you can get item $$$3$$$ from item $$$1$$$ using the second trader since $$$s_1 = 3 \gt 1 = s_3$$$. After the third update, it is still possible to get any item starting with any item. For instance, if you start with item $$$2$$$ and want to get item $$$1$$$, you can first exchange your item $$$2$$$ for item $$$3$$$ using the second trader, and then exchange item $$$3$$$ for item $$$1$$$ using the first trader.

Exchange Queries

Examples