您在一个市场,有两个交易者愿意交易 $$$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)$$$ 对的数量,这样在第一个 $$$k$$$ 更新后,项目 $$$i$$$ 至少与项目 $$$j$$$ 一样有价值。
示例
输入复制
23 31 2 33 2 12 1 32 1 31 1 24 23 2 4 13 1 4 21 1 32 1 3
输出复制
6991211
注意
在第一个测试用例中,第一次更新后,两个排列都是恒等排列,因此唯一有效的对是 $$$(1, 1)$$$、$$$(2, 1)$$$、$$$(2, 2)$$$、$$$(3, 1)$$$、$$$(3, 2)$$$ 和 $$$(3, 3)$$$。第二次更新后,可以获得任何物品开头的任何物品。例如,您可以使用第二个交易者从项目 $$$1$$$ 获取项目 $$$3$$$,因为 $$$s_1 = 3 \gt 1 = s_3$$$。第三次更新后,仍然可以获得任何物品开头的任何物品。例如,如果您从物品$$$2$$$开始并想要获得物品$$$1$$$,您可以先使用第二个交易者将物品$$$2$$$兑换成物品$$$3$$$,然后使用第一个交易者将物品$$$3$$$兑换成物品$$$1$$$。