Intersection of Permutations

Description:

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — the number of elements in both permutations and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — permutation $$$a$$$. It is guaranteed that each value from $$$1$$$ to $$$n$$$ appears in $$$a$$$ exactly once.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$) — permutation $$$b$$$. It is guaranteed that each value from $$$1$$$ to $$$n$$$ appears in $$$b$$$ exactly once.

Each of the next $$$m$$$ lines contains the description of a certain query. These are either:

• $$$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$$$).

Output:

Print the answers for the queries of the first type, each answer in the new line — the number of values which appear in both segment $$$[l_a; r_a]$$$ of positions in permutation $$$a$$$ and segment $$$[l_b; r_b]$$$ of positions in permutation $$$b$$$.

Sample Input:

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

Sample Output:

1
1
1
2
0

Note:

Consider the first query of the first example. Values on positions $$$[1; 2]$$$ of $$$a$$$ are $$$[5, 1]$$$ and values on positions $$$[4; 5]$$$ of $$$b$$$ are $$$[1, 4]$$$. Only value $$$1$$$ appears in both segments.

After the first swap (the second query) permutation $$$b$$$ becomes $$$[2, 1, 3, 5, 4, 6]$$$.

After the second swap (the sixth query) permutation $$$b$$$ becomes $$$[5, 1, 3, 2, 4, 6]$$$.