题目描述

给你两个长度为 $n$ 的序列 $a$ 和 $b$ ，它们都是由 $1\sim n$ 组成的排列。

即 $a$ 中 $1$ 到 $n$ 的每个数都正好出现一次，$b$ 也是这样。

你需要对它们进行查询：

• $1\ l\ r\ x\ y$，查询有多少个数既在 $a_l\sim a_r$ 中出现，又在 $b_x\sim b_y$ 中出现。

输入格式

第一行包含两个整数 $n$ 和 $m$，两个排列中的元素个数和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$

接下来的 $m$ 行，每行对应一个询问，格式如题面描述。

输出格式

对于每个第一种查询，输出一行一个整数，为对应的答案。

6 4
5 1 4 2 3 6
2 5 3 1 4 6
1 1 2 4 5
1 2 3 3 5
1 1 6 1 2
1 4 4 1 3

1
2
2
1

数据规模与约定

$n\le 5000$，$m\le 2\times 10^5$，其他所有数据保证合法。

来源

https://codeforces.com/problemset/problem/1093/E