给你两个排列 $$$a$$$ 和 $$$b$$$,两者都由 $$$n$$$ 元素组成。 $$$n$$$ 元素的排列是一个整数序列,从 $$$1$$$ 到 $$$n$$$ 的每个值在其中只出现一次。
您需要使用它们执行两种类型的查询:
- $$$1~l_a~r_a~l_b~r_b$$$ — 计算两个段中出现的值的数量 $$$[l_a; r_a]$$$ 排列 $$$a$$$ 中的位置和段 $$$[l_b; r_b]$$$排列中的位置$$$b$$$;
- $$$2~x~y$$$ — 在排列 $$$b$$$ 中交换位置 $$$x$$$ 和 $$$y$$$ 上的值。
打印第一种类型的每个查询的答案。
保证输入中至少有一个第一类型的查询。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — 两个排列中的元素数量和查询数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 排列 $$$a$$$。保证从 $$$1$$$ 到 $$$n$$$ 的每个值在 $$$a$$$ 中恰好出现一次。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$) — 排列 $$$b$$$。保证从 $$$1$$$ 到 $$$n$$$ 的每个值在 $$$b$$$ 中恰好出现一次。
接下来的 $$$m$$$ 行中的每一行都包含某个查询的描述。这些是:
- $$$1~l_a~r_a~l_b~r_b$$$ ($$$1 \le l_a \le r_a \le n$$$, $$$1 \le l_b \le r_b \le n$$$);
- $$$2~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$)。
输出
打印第一类查询的答案,新行中的每个答案 — 两个段中出现的值的数量 $$$[l_a; r_a]$$$ 排列 $$$a$$$ 中的位置和段 $$$[l_b; r_b]$$$ 排列中的位置 $$$b$$$。
示例
输入 #1
6 7 5 1 4 2 3 6 2 5 3 1 4 6 1 1 2 4 5 2 2 4 1 1 2 4 5 1 2 3 3 5 1 1 6 1 2 2 4 1 1 4 4 1 3
输出 #1
1 1 1 2 0
注意
考虑第一个示例的第一个查询。仓位价值 $$$[1; $$$a$$$ 中的 2]$$$ 为 $$$[5, 1]$$$ 以及 $$$[4 位置上的值; $$$b$$$ 中的 5]$$$ 为 $$$[1, 4]$$$。仅值 $$$1$$$ 出现在两个段中。
第一次交换(第二个查询)后,排列 $$$b$$$ 变为 $$$[2, 1, 3, 5, 4, 6]$$$。
第二次交换(第六次查询)后,排列 $$$b$$$ 变为 $$$[5, 1, 3, 2, 4, 6]$$$。