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.